[Computational Complexity] Favorite Theorems Recap
In 1994, I listed My Favorite Ten Complexity Theorems of the Past Decade in conjunction with an invited talk at that year's FST&TCS conference. Over this past year in this weblog I went back and picked my favorite ten complexity theorems of the decade since that first paper.
- Derandomization (Impagliazzo-Wigderson)
- Primality (Agrawal-Kayal-Saxena)
- Probabilistically Checkable Proofs (Håstad)
- Connections (Trevisan)
- Superlinear Bounds on Branching Programs (Ajtai)
- Parallel Repetition (Raz)
- List Decoding (Sudan)
- Learning Circuits (Bshouty-Cleve-Gavaldà-Kannan-Tamon)
- Quantum Lower Bounds (Ambainis)
- Derandomizing Space (Saks-Zhou)
We'll do this again in ten.
Posted by Lance to Computational Complexity at 12/21/2004 06:39:02 AM