Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Turing Award winner and former Oxford professor Tony Hoare passed away last Thursday at the age of 92. Hoare is famous for quicksort, ALGO...

I posted on When did Math get so hard? a commenter pointed out that one can also ask When did Computer Science Theory Get so Hard? For t...

In the fall of 1976 I started as a Freshman at SUNY Stony Brook intending to major in Math and Computer Science. I took Honors Calculus I a...

Scientific American writes about rescuing the enormous theorem (classification of finite simple groups) before the proof vanishes. How can...

Just as I was complaining that we haven't seen many surprising breakthroughs in complexity recently, we get an earthquake of a result to st...

THE 17x17 PROBLEM HAS BEEN SOLVED!!!!! On Nov 30, 2009 I posted here the following challenge: If someone emails me a 4-coloring of...

David Zuckerman The 2025 Gödel Prize has been awarded to Eshan Chattopadhyay and David Zuckerman for their paper Explicit two-source extrac...

On October 8th, when in my graduate complexity course as we discussed the 1987 Razborov-Smolensky result that one can't compute the Mod p b...

The 17x17 challenge: worth $289.00. I am not kidding. Definition: The n x m grid is c-colorable if there is a way to c-color the vertic...