Explore advanced computational complexity theory through this comprehensive graduate-level lecture series from Carnegie Mellon University's 15-855 course taught by Ryan O'Donnell in Fall 2017. Master the fundamental concepts needed to begin complexity theory research, building upon undergraduate knowledge equivalent to completing Sipser's textbook. Delve into hierarchy theorems covering time, space, and nondeterministic complexity classes, then progress through circuit complexity, probabilistic complexity classes, and the polynomial time hierarchy. Examine key theorems including the Hopcroft-Paul-Valiant theorem, quasilinear Cook-Levin theorem, and Valiant-Vazirani theorem. Study interactive proof systems, Arthur-Merlin classes, and the relationship between IP and PSPACE. Investigate counting complexity through #P-completeness and the permanent, alongside algebraic circuit complexity and its connections to Boolean complexity. Analyze circuit lower bounds using random restrictions, the switching lemma, and Razborov-Smolensky techniques for AC0 circuits. Explore the hardness versus randomness paradigm, hardness amplification methods, and advanced topics in uniform ACC lower bounds through Toda's theorems.

Syllabus

Course Introduction and Overview: Graduate Complexity Lecture 1 at CMU
Hierarchy Theorems (Time, Space, and Nondeterministic): Graduate Complexity Lecture 2 at CMU
Hopcroft--Paul--Valiant Theorem: Graduate Complexity Lecture 3 at CMU
Circuits: Graduate Complexity Lecture 4 at CMU
Probabilistic Complexity Classes: Graduate Complexity Lecture 5 at CMU
Quasilinear Cook--Levin Theorem: Graduate Complexity Lecture 6 at CMU
The Polynomial Time Hierarchy: Graduate Complexity Lecture 7 at CMU
Oracles, and the Polynomial Time Hierarchy vs. circuits: Graduate Complexity Lecture 8 at CMU
Improving Kannan's Theorem: Graduate Complexity Lecture 8 bonus material at CMU
Time/Space Tradeoffs for SAT: Graduate Complexity Lecture 9 at CMU
Introduction to Arthur-Merlin classes, MA and AM: Graduate Complexity Lecture 10 at CMU
More on constant-round interactive proof systems: Graduate Complexity Lecture 12 at CMU
Approximate counting: Graduate Complexity Lecture 12 at CMU
Valiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexity Lecture 13 at CMU
Toda's 1st Theorem and the Permanent: Graduate Complexity Lecture 14 at CMU
Permanent is #P-complete: Graduate Complexity Lecture 20 (out of order) at CMU
Algebraic Circuit Complexity: Graduate Complexity Lecture 15 at CMU
Algebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMU
Instance Checking and the Permanent: Graduate Complexity Lecture 16 at CMU
IP = PSPACE: Graduate Complexity Lecture 17 at CMU
Random Restrictions and AC0 Circuit Lower Bounds: Graduate Complexity Lecture 18 at CMU
The Switching Lemma: PRST version: Graduate Complexity Lecture 19 at CMU
Monotone circuit lower bounds: Graduate Complexity Lecture 21 at CMU
Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMU
Toda's 2nd Theorem and lower bounds for uniform ACC: Graduate Complexity Lecture 23 at CMU
Hardness vs. Randomness I: Graduate Complexity Lecture 24 at CMU
Hardness vs. Randomness II: Graduate Complexity Lecture 25 at CMU
Hardness amplification: Graduate Complexity Lecture 26 at CMU
Ironic complexity: Graduate Complexity Lecture 27 at CMU