Computational Complexity

 At the workshop  Ramsey Theory: Yesterday, Today, and Tomorrow, Edited by Alexander Soifer, 2011. (There is a printed proceedings that you ...

Two of my colleagues and co-authors from my early days at the University of Chicago have released books over the past few months designed to...

Jimmy Buffett passed away on Sept 1, 2023. His Wikipedia entry (see  here ) says his death was peaceful and he was surrounded by friends, fa...

In this weblog, we've used constructive in different ways. Often we talk about constructive as something we can create in polynomial tim...

I was recently asked by a non-mathematician about the difference between the terms Theorem, Lemma, etc. My first reaction was I probably hav...

When I start a new academic job, I need to prove that I actually have a PhD. I have to log in my MIT alumni page, pay my $10 and they email ...

There are some people who believe that we are all characters in a video game written by Abisola (this is sometimes called The   S i mulation...

I turn sixty today, spending my birthday reviewing a computer science department in Asia. Sixty is a good time to look back and reflect in a...

When I taught Programming for Engineers  at Northwestern in 2008, the textbook gave access to PowerPoint slides I could use to teach the cla...

This post is about an open problems column by Gasarch-Gezalyn-Patrick so they can be considered co-authors on this post. The column is here ...

My wife's cousin and her daughter came and visited Chicago. The daughter, between junior and senior year of high school, is on the tail ...

 I was giving a recruiting talk for my REU program and I had some slides with testimonials from students: ----------------------------------...

 A twitter question from a young researcher. Wait, how do paper writing collaborations work with LaTeX that doesn’t use overleaf? You need...

(I covered a simlar topic  here .)   In the June 2023 issue of The Atlantic is an article titled:                                     Never...

Back in May I posted about a paper that finds primes pseudodeterministically and Quanta magazine recently published a story on the result...

In 1983, as a grad student, I knew that HALT \( \le_T \) KOLG but didn't know how to prove it. I asked around and A MONTH later through ...

Twitter tells me it's my twitterversary, 15 years since I first started tweeting. Not sure I'll make it to sweet sixteen. No longer ...

Ravi Boppana recently did a guest blog on Chernoff turning 100 for us  here .  Consider this unpublished comment on that post:    ----------...

The New York Times published an article with the ominous title A.I. Is Coming for Mathematics, Too . We know by the work of Gödel and Turing...

Guest post by Ravi Boppana Herman Chernoff  celebrates a milestone today: he turns 100 years old.  We in theoretical computer science know...