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)

The purpose of these endeavors is not just to have a top ten list but to use these great results to highlight several areas in computational complexity where we have seen significant progress in recent years. Ten areas do not do justice to complexity and we also have great results in proof complexity, Kolmogorov complexity, constructions of expanders and extractors, zero-knowledge proofs and structural complexity.

We'll do this again in ten.