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
| 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 | 8 |
Any gaps could be due to errors when fetching the blog’s feed.
Most recent posts
Guest post by Martin BullingerVery recently, Vijay Vazirani's paper A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length got accepted to Mathematics of Operations Research. For the first time, it gives …
I posted (see here) about Avi Wigderson being a counterexample to two of G.H. Hardy's opinions:1) Hardy thought Math was a young man's game. I got some good comments on this. Some agreed and some …
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 …