15-855: Graduate Computational Complexity Theory, Fall 2017


Meeting time and place: Tuesday and Thursday, 10:30am-11:50am, GHC 4303.
Course bulletin board: Piazza. This will be used for all course-related communications.
Course grading: Gradescope. Course entry code: M3YGWX
Instructor: Ryan O'Donnell (Office Hours: Fri. 3:30-4:30, GHC7213)
TAs: Ellis Hershkowitz (Office Hours: Mon. 1:00-3:00, GHC9219), Nicolas Resch (Office Hours: Sun. 3:00-4:00, GHC7507)
Textbook: Computational Complexity: A Modern Approach, by Arora and Barak.

Lecture 01: Overview of the course Review: Arora--Barak Chapters 1 (except 1.7), 2, and 4
Lecture 02: Time (and space) hierarchy theorems Reading: Arora--Barak Chapters 3.1, 3.2; also 1.7 if you're interested in the O(T log T) simulation
Lecture 03: Hopcroft--Paul--Valiant Theorem Reading: The original paper
Lecture 04: Circuits Reading: Arora--Barak Chapters 6.1--6.7
Lecture 05: Probabilistic complexity classes Reading: Arora--Barak Chapters 7.1--7.5 (except not 7.5.2)

Homework assignments

Course description

Prerequisite: An undergraduate course in computational complexity theory, covering most of "Part III" of Sipser and/or most of Carnegie Mellon's 15-455.

Potential topics: Models and Time Hierarchy Theorem. Nondeterminism, padding, Hopcroft-Paul-Valiant Theorem. Circuits and advice. Randomized classes. Cook-Levin Theorem and SAT. Nondeterministic Time Hierarchy Theorem, and nondeterministic models. Oracles, alternation, and the Polynomial Time Hierarchy. Kannan's Theorem, Karp-Lipton, and PH vs. constant-depth circuits. Time-Space tradeoffs for SAT. Randomized classes vs. PH. Interactive proofs and the AM hierarchy. NP in BPP implies PH in BPP, and Boppana-Hastad-Zachos. BCGKT Theorem and Cai's Theorem. Counting classes and the permanent. Valiant's Theorem. Algebraic Complexity. IP = PSPACE and interactive proofs. Instance checkers and Santhanam's Theorem. Random restrictions and AC0 lower bounds for parity. Monotone circuit lower bounds. Razborov-Smolensky lower bounds for AC0[p]. Valiant-Vazirani and Toda Theorems. Beigel-Tarui Theorem. Hardness vs. Randomness and Nisan-Wigderson. Hardness amplification and derandomization. Williams's Theorem. Natural proofs and barriers.


There will be 11 homeworks, and two take-home "tests".

Your final grade will be determined from your final point total out of 380.

Well-being and happiness

Your well-being and happiness is very important to us at CMU, and there are many resources to help you with it. Please contact me directly if you need assistance or would like to talk about any such issues.

Homework instructions

Test instructions

Additional resources

Let me know if your favorite book or set of lecture notes does not appear here!


Lecture notes: