Tuesday, December 21, 2004

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. 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.


  1. Do you plan to publish a survey of these ten results as in 1994?