Computational Complexity

 I have a website devoted to parodies of the song                 I am the very model of a modern major general  here . So I sometimes look ...

Each fall I try to predict the upcoming job market for theoretical computer science faculty and give suggestions to those pursuing these pos...

LANCE: You should take a break from all the AI stuff and talk about your book! BILL: I will!  But it's not my book  its co-authored with...

When the Clay Mathematics Institute announced the Millennium Prize Problems back in 2000, we joked that if you proved P = NP, you wouldn...

(Throughout this post I will assume that the recent results by OpenAI and Anthropic contain correct proofs of what they claim.) I wrote the ...

In this week's big news (though it's only Wednesday), OpenAI announced a proof that the exponential-time hypothesis is false , with...

(Lance and Bill did a vidcast about the OpenAI Document Drop. See  here . My spellcheck thinks that vidcast and OpenAI are not words.)   The...

In fall of 1985 when I started graduate school, my advisor Michael Sipser asked me to read an early handwritten manuscript by Johan Håstad o...