Computational Complexity

In response to my blog post about how its easier to FIND novelty songs (and other things) than it used to be (see  here ) Lance showed how e...

Invited Speaker Nutan Limaye, Conference Chair Valentine Kabanets, 2024 PC Chair Rahul Santhanam, myself, 2025 PC Chair Srikanth Srinivasan ...

On June 21, 1993, at the Issac Newton Institute for Mathematical Science, Andrew Wiles announced that he had proven Fermat's Last Theore...

The quantum factoring algorithm of Peter Shor ( FOCS 1994, SIAM Review  1999) turns thirty this year. Before his algorithm, quantum computi...

In a post from 2015 I noted that the word quantum is often misused (see here ). Have things gotten better since then? I think you know the ...

June Edition Two decades ago, I named the recently departed Luca Trevisan's paper connecting extractors to psuedorandom generators as o...

 Trump is pondering who to pick for his vice president. For a recent podcast about it go  here . Spoiler alert: Doug B or Marco R or J.D. Va...

Avi Wigderson gave his ACM Turing Award lecture last week, and instead of telling his own story, he focused on Alan Turing and his influenc...

 In 2013 I wrote a blog to celebrate Lance's 50th birthday by contrasting what things were like when Lance was 10 to when he was 50. Tha...

Why do we have two complexity classes for exponential time, E and EXP? First the definitions: E is the set of problems computable in time \(...

As you all know Luca Trevisan, a Giant in our field, passed away at the too-young age of 52. See Lance's post on Luca HERE.  As the edit...

Complexity theorist  Luca Trevisan  lost his battle to cancer yesterday in Milan at the age of 52. A terrible loss for our community and our...

I've argued that more and more we seem to live in an Optiland , a computational utopia where through recent developments in optimization...

I recently came across (by accident) the link to all of the BEATCS complexity columns from 1987 to the 2016. See HERE . (If you know a link ...

LANCE: I had my first Quanta Article published! I explore computation, complexity, randomness and learning and feeling the machine. BILL: F...

May Edition Most of my favorite theorems tell us something new about the world of complexity. But let's not forget the greatest technica...

For this post all Context Free Grammars (henceforth CFGs) are assumed to be in Chomsky Normal Form. The size of a CFG \(G\)  is the number o...

On the plane earlier this week I got around to watching the Academy Award winning movie  Godzilla Minus One , one of the best monster movies...

 The call for nominations for the Test of Time Award at FOCS 2024 has been posted  here . Eligibility and past winners are  here . Points 1)...

It started with a post from  Fermat's Library . 132 is the sum of all the 2-digit numbers made from its digits. It is the smallest such...