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