Now in one place all of my sixty favorite theorems from the six decades of computational complexity (1965-2024).
2015-2024
- Graph Isomorphism (Babai)
- Sensitivity (Huang)
- Quantum Provers (Ji-Natarajan-Vidick-Wright-Yuen)
- Dichotomy (Bulatov, Zhuk)
- Algebraic Circuits (Limaye-Srinivasan-Tavenas)
- Extracting Ramsey Graphs (Chattopadhyay-Zuckerman)
- Random Oracles (Håstad-Rossman-Servedio-Tan)
- Parity Games (Calude-Jain-Khoussainov-Li-Stephan)
- Gradient Descent (Fearnley-Goldberg-Hollender-Savani)
- Learning from Natural Proofs (Carmosino-Impagliazzo-Kabanets-Kolokolova)
- Undirected Connectivity in Log Space (Reingold)
- Optimal Inapproximability for Max-Cut (Khot-Kindler-Mossel-O'Donnell, Mossel-O'Donnell-Oleszkiewicz)
- Limitations of linear programming (Fiorini-Massar-Pokutta-Tiwary-de Wolf, Rothvoß)
- Complexity of Nash Equilibrium (Daskalakis-Goldberg-Papadimitriou, Chen-Deng)
- Combinatorial Proof of PCP Theorem (Dinur)
- Constructive Proof of the Lovász Local Lemma (Moser)
- Polylogarithmic independence fools AC0 (Braverman)
- QIP = PSPACE (Jain-Ji-Upadhyay-Watrous)
- Lower Bounds on Multilinear Formulas (Raz)
- NEXP not in ACC0 (Williams)
- 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)
1985-1994
To mark my first decade in computational complexity during my pre-blog days, I chose my first set of favorite theorems from that time period for an invited talk and paper (PDF) at the 1994 Foundations of Software Technology and Theoretical Computer Science (FST&TCS) conference in Madras (now Chennai), India. The links below go to the papers directly, except for Szelepcsényi’s, which I can't find online.
- Branching Programs (Barrington)
- Bounded-Depth Circuits (Håstad)
- Monotone Circuits (Razborov)
- Nondeterministic Space (Immerman, Szelepcsényi)
- Cryptographic Assumptions (Impagliazzo-Levin-Luby)
- Isomorphism Conjecture (Ogihara-Watanabe)
- Simulating Randomness (Nisan)
- Counting Complexity (Toda)
- Counting Classes (Beigel-Reingold-Spielman)
- Interactive Proof Systems (Arora-Lund-Motwani-Sudan-Szegedy)
1975-1984 (From 2006)
- Alternation (Chandra-Kozen-Stockmeyer)
- Relativization (Baker-Gill-Solovay)
- Small Sets (Mahaney)
- Primality Algorithms (Solovay-Strassen, Miller, Rabin)
- Probabilistic Complexity (Gill, Sipser)
- The Permanent (Valiant)
- Unique Witnesses (Valiant-Vazirani)
- Parity (Furst-Saxe-Sipser, Ajtai)
- The Yao Principle (Yao)
- Nonuniform Complexity (Karp-Lipton)
1965-1974 (From 2005)
- The Seminal Paper (Hartmanis-Stearns)
- Efficient Computation (Cobham-Edmonds)
- NP-Completeness (Cook, Levin)
- Combinatorial NP-Complete Problems (Karp)
- The Polynomial-Time Hierarchy (Meyer-Stockmeyer)
- P = NP for Space (Savitch)
- Abstract Complexity (Blum)
- NP-Incomplete Sets (Ladner)
- Logical Characterization of NP (Fagin)
- Defining the Future (Cook-Reckhow)
Will I do this again in ten years when I'm 70? Come back in 2034 and find out.
No comments:
Post a Comment