15-855: Graduate Computational Complexity Theory, Fall 2017 (original) (raw)
Lecture 01:
Review: Arora--Barak Chapters 1 (except 1.7), 2, and 4
Lecture 02:
Hierarchy theorems: time, space, and nondeterministic versions
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:
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)
Lecture 06:
Quasilinear Cook--Levin Theorem
Reading: Section 2.3.1 in this survey by van Melkebeek, these slides by Viola
Lecture 07:
The Polynomial Time Hierarchy and alternation
Reading: Arora--Barak Chapters 5.1--5.3
Lecture 08:
Oracles, and the Polynomial Time Hierarchy vs. circuits
Reading: Arora--Barak Chapters 5.5, 6.4. Bonus: improving Kannan's Theorem.
Lecture 09:
Reading: Arora--Barak Chapter 5.4
Lecture 10:
Intro to Merlin-Arthur protocols: MA and MA
Reading: Arora--Barak Chapter 8.2.0
Lecture 11:
More on constant-round interactive proof systems
Reading: Arora--Barak Chapter 8.2.4, Chapter 8 exercises
Lecture 12:
Reading: Arora--Barak Chapter 8.2.1, 8.2.2
Lecture 13:
Valiant--Vazirani Theorem and exact counting (#P)
Reading: Arora--Barak Chapters 17.0, 17.1, 17.2.1, 17.3.2, 17.4.1
Lecture 14:
Toda's 1st Theorem, and the Permanent
Reading: Arora--Barak Chapters 17.4, 8.6.2, 17.3.1
Lecture 20 (sic):
Reading: PowerPoint slides
Lecture 15:
Reading: Arora--Barak Chapter 16.1. Bonus: "algebraic NP vs. P" vs. "Boolean NP vs. P".
Lecture 16:
Instance checking and the Permanent
Reading: Arora--Barak Chapter 8.6
Lecture 17:
Reading: Arora--Barak Chapters 8.3, 8.4
Lecture 18:
Random restrictions and AC0 lower bounds
Reading: Arora--Barak Chapter 14.1
Lecture 19:
Reading: My old notes on Razborov's proof
Lecture 21:
Reading: Arora--Barak Chapter 14.3
Lecture 22:
Razborov-Smolensky lower bounds for AC0[p]
Reading: Arora--Barak Chapter 14.2
Lecture 23:
Toda's 2nd Theorem & lower bounds for uniform ACC
Reading: Arora--Barak Chapters 17.4.4, 14.4.2; and, B.2 of the Web Addendum (with correction)
Lecture 24:
Reading: Arora--Barak Chapters 20.0, 20.1
Lecture 25:
Reading: Arora--Barak Chapters 20.2
Lecture 26:
Reading: Arora--Barak Chapters 19.0, 19.1
Lecture 27:
Reading: Arora--Barak Web Addendum
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 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.