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.
Handwritten lecture notes and homework in one giant (120MB) pdf
YouTube playlist for lectures (though the below Panopto links may be preferable) Lectures
Lecture 01: | Overview of the course | 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: | 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) |
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: | Time/space tradeoffs for SAT | 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: | Approximate counting | 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): | Permanent is #P-complete | Reading: PowerPoint slides |
Lecture 15: | Algebraic circuit complexity | 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: | IP = PSPACE | Reading: Arora--Barak Chapters 8.3, 8.4 |
Lecture 18: | Random restrictions and AC0 lower bounds | Reading: Arora--Barak Chapter 14.1 |
Lecture 19: | The Switching Lemma | Reading: My old notes on Razborov's proof |
Lecture 21: | Monotone circuit lower bounds | 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: | Hardness vs. Randomness I | Reading: Arora--Barak Chapters 20.0, 20.1 |
Lecture 25: | Hardness vs. Randomness II | Reading: Arora--Barak Chapters 20.2 |
Lecture 26: | Hardness amplification | Reading: Arora--Barak Chapters 19.0, 19.1 |
Lecture 27: | Ironic Complexity | 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.
EvaluationThere will be 11 homeworks, and two take-home "tests".
- Homeworks will come out on Tuesdays and be due on Tuesdays.
- Homeworks will have 3 problems, each worth 10 points. Due to TA time limitations, only 2 out of the 3 problems will be graded.
- The two take-home "tests" will be Oct. 10 -- Oct. 17 and Nov. 30 -- Dec. 7.
- The tests will have 4 problems, each worth 20 points. All 4 problems will be graded.
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- All homework must be typeset, with PDFLaTeX highly encouraged.
- For LaTeX help, I recommend the book More Math Into LaTeX by Grätzer and also the website TeX Stack Exchange.
- Homework must be turned in on Gradescope; it will generally be due Tuesdays at 10am.
- You have six (6) "late days" for use on homework throughout the semester.
- No more than 3 late days can be used on any one assigment.
- Any amount of time between 1 minute and 24 hours counts as one late day.
- You are responsible for knowing how many late days you have left. If you are unsure, you could ask a TA.
- Except through the use of late days described above, no late homework will be accepted. If you are out of late days and your homework is late, you will get 0 points.
- You may discuss homework problems with others in the class. However, you should not share any written notes, and of course all your writeups should be done individually.
- Homework will be graded both for correctness and for clarity of exposition.
- Same instructions as for the homework, except: no late days may be used, and no collaboration of any sort allowed.
Let me know if your favorite book or set of lecture notes does not appear here!
Textbooks:
- Computational Complexity: A Modern Approach, by Arora and Barak
- Computational Complexity, by Papadimitriou
- Theory of Computational Complexity, by Du and Ko
- Complexity Theory, by Wegener
- Computational Complexity: A Conceptual Perspective, by Goldreich
- The Complexity Theory Companion, by Hemaspaandra and Ogihara
- Theory of Computation, by Kozen
- Computability and Complexity Theory, by Homer and Selman
- Structural Complexity I and II, by Balcázar, Díaz, and Gabarró
- Boolean Function Complexity: Advances and Frontiers, by Jukna
- The Nature of Computation, by Moore and Mertens
- Introduction to the Theory of Computation, by Sipser
- Van Melkebeek: 2007, 2010, 2011, 2015, 2016
- Harsha: '11/'12, '12/'13, '13/'14
- Trevisan: 2001, 2002, 2004,2008,2010,2012,2014
- Sudan: 2002,2003,2007,2009
- Spielman: 1998, 1999, 2000, 2001
- Moshkovitz: 2012, 2016
- Katz: 2005, 2011
- Umans
- Hansen 2010
- Vadhan 2002
- Cai
- Gács and Lovász
- Beame 2008
- Arora 2001
- Miltersen 2006
- Håstad
- M. Naor '04/'05
- Guruswami--O'Donnell 2009