My Favorite Ten Complexity Theorems of the Past Decade
Lance Fortnow
University of Chicago
My Favorite Ten Complexity Theorems of the Past Decade
Why pick ten theorems?
Ground Rules
Branching Programs
Favorite Theorem 1
Applications
Bounded-Depth Circuits
Favorite Theorem 2
Other Techniques
Monotone Circuits
Favorite Theorem 3
More Monotone Results
Failure of Circuit Complexity
Nondeterministic Space
Favorite Theorem 4
Related Closure Results
Cryptographic Assumptions
Three Usual Assumptions
Favorite Theorem 5
Isomorphism Conjecture
Density of Complete Sets
Favorite Theorem 6
Simulating Randomness
Favorite Theorem 7
Reducing Error
Counting Complexity
Favorite Theorem 8
Applications
Counting Classes
Favorite Theorem 9
Other Counting Classes
Interactive Proof Systems
Relationships to Other Classes
Favorite Theorem 10
Conclusions