Skip to content

Computational Complexity

Computational Complexity and other fun stuff in math and computer science.

  • By Lance Fortnow, Bill Gasarch
  • Based in United States of America
  • Roughly two posts per week
  • First post on

Posts per month

Data for this chart is available in the table below
Posts per month
Month starting Posts
Dec 2022 5
Jan 2023 8
Feb 2023 8
Mar 2023 8
Apr 2023 7
May 2023 9
Jun 2023 6
Jul 2023 9
Aug 2023 8
Sep 2023 7
Oct 2023 8
Nov 2023 8
Dec 2023 6
Jan 2024 10
Feb 2024 8
Mar 2024 8
Apr 2024 6

Any gaps could be due to errors when fetching the blog’s feed.

Most recent posts

Favorite Theorems: Quantum Provers
For our next favorite theorem, we look at the surprising power of provers who share entangled bits. If you can prove something to an arbitrarily computable verifier, then two entangled provers can convince a polynomial-time …
On , by Lance Fortnow, 356 words
Avi Wigderson is a counterexample to TWO stupid thoughts of G.H. Hardy
Recently1) Avi Wigderson won the Turing Award (See blog posts by Fortnow-here, Scott-here, Lipton-Regan here, and the ACM announcement here). The last time I could find when Fortnow-Gasarch, Scott, Lipton-Regan all blogged on the same …
On , by gasarch, 576 words
Avi wins the Turing Award
The ACM announced that Avi Wigderson, a force in computational complexity and beyond, will receive the 2023 A. M. Turing Award (Quanta article). This is the first primarily complexity theorist to win the award since …
On , by Lance Fortnow, 280 words