# 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