CS 254: Computational Complexity
General Information
Instructor: Li-Yang Tan
CAs: Caleb Koch (ckoch@stanford.edu)
Amalee Wilson (amalee@stanford.edu)
Time: Mondays and Wednesdays, 3:00-4:20pm
Amalee's OH: Tuesdays 6:30-8:30pm
Caleb's OH: Fridays 3-5pm
Li-Yang's OH: After class by appointment
CAs: Caleb Koch (ckoch@stanford.edu)
Amalee Wilson (amalee@stanford.edu)
Time: Mondays and Wednesdays, 3:00-4:20pm
Amalee's OH: Tuesdays 6:30-8:30pm
Caleb's OH: Fridays 3-5pm
Li-Yang's OH: After class by appointment
Textbooks
Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Mathematics and Computation, by Avi Wigderson.
Mathematics and Computation, by Avi Wigderson.
List of Topics
- Space Complexity
ST-connectivity and its role in space complexity
Non-determinism in space complexity: Savitch's theorem
NL = coNL: Immerman-Szelepcsényi theorem
- Polynomial Hierarchy
P, NP, coNP, and friends
NP ∩ coNP ≈ having a good characterization
Efficient computation in a world where P = NP - Randomized Complexity
Randomness as a resource. Does P = BPP?
Randomness versus non-determinism
Unique-SAT: Valiant-Vazirani theorem - Non-Uniform Computation
Circuit complexity
Randomness versus non-uniformity: Adelman's theorem
Small circuits for NP? Karp-Lipton theorem
- Interactive Proofs
Arthur and Merlin, and generalizations of NP
Approximate counting: Goldwasser-Sipser theorem
IP = PSPACE
Lecture schedule
(Will be updated as the quarter progresses. Supplementary material listed in gray.)
- Lecture 1: Course overview; the grand challenges of complexity theory
Chapter 3.4 of Wigderson's book: The P versus NP question, its meaning and importance
Gödel's 1956 letter to von Neumann
- Lecture 2: CS154 recap
- Lecture 3: Space complexity; Savitch’s theorem (AB §4.1-4.3)
- Lecture 4: Nondeterministic space and NL-completeness of STCONN (AB §4.4)
The complexity of graph connectivity, Avi Wigderson
Undirected connectivity in log-space, Omer Reingold - Lecture 5: Immerman-Szelepcsényi theorem (AB §4.4)
- Lecture 6: NP, coNP, and NP ∩ coNP (AB §2.6-2.7)
Chapter 3.5 of Wigderson's book: The class coNP, the NP versus coNP question, and efficient characterization
Chapter 6 of Wigderson's book: Proof complexity
Propositional proof complexity: past, present, and future, Paul Beame and Toniann Pitassi
The limits of proof, video of a talk by Paul Beame
Proof complexity 2020, video of a talk by Paul Beame
- Lecture 7: The polynomial hierarchy (AB §5)
Completeness in the polynomial-time hierarchy, Marcus Schaefer and Chris Umans
- Lecture 8: PSAT and oracle Turing machines (AB §5)
- Lecture 9: The power of randomness in computation (AB §7)
Chapter 7 of Wigderson's book: Randomness in computation
Finding hay in haystacks: the power and limits of randomness, video of a talk by Avi Wigderson
Pseudorandomness, monograph by Salil Vadhan - Lecture 10: Randomized complexity. P versus BPP; NP versus BPP (AB §7)
Pure randomness extracted from two poor sources, Don Monroe
How random is your randomness, and why does it matter, Eshan Chattopadhyay and David Zuckerman
Research Vignette: Ramsey graphs and the error of explicit 2-source extractors, Amnon Ta-Shma
- Lecture 11: Non-uniform computation and circuit complexity (AB §6)
Chapter 5 of Wigderson's book: Lower bounds, boolean circuits, and attacks on P vs. NP
P =? NP, Scott Aaronson
Some estimated likelihoods for computational complexity, Ryan Williams
- Lecture 12: Relating P/poly to BPP and NP: Adelman's theorem and the Karp-Lipton theorem (AB §6)
- Lecture 13: Interactive proofs (AB §8)
Chapter 10 of Wigderson's book: Randomness in proofs
Proofs, Knowledge, and Computation, video of a talk by Silvio Micali
A history of the PCP theorem, Ryan O'Donnell
E-mail and the unexpected power of interaction, László Babai
1993 Gödel prize citation, for Babai-Moran and Goldwasser-Micali-Rackoff - Lecture 14: Interactive proof for #3SAT (AB §8)
- Lecture 15: Arthur and Merlin
- Lecture 16: Goldwasser-Sipser AM protocol for approximate counting
- Lecture 17: Unique-SAT and the Valiant-Vazirani theorem
- Lecture 18: Ask Me Anything
Evaluation
(Tentative; subject to change.)
• 4 problem sets (70%, weighted by total score per set)
• Course project (30%)
☐ Interim progress report (5%)
☐ Final written report (15%)
☐ Your peer evaluation report (10%)
• CR: ≥ 70% on 2 psets or ≥ 70% on Course project
Policies:
• Course project (30%)
☐ Interim progress report (5%)
☐ Final written report (15%)
☐ Your peer evaluation report (10%)
• CR: ≥ 70% on 2 psets or ≥ 70% on Course project
• 4 late days, ≤ 2 per pset, ≤ 1 for interim report, ≤ 1 for final report
• Late days cannot be used for the peer evaluation report
• Each late day counts towards each group member's quota
• Regrade requests must be submitted within 1 week
• Late days cannot be used for the peer evaluation report
• Each late day counts towards each group member's quota
• Regrade requests must be submitted within 1 week
Coursework schedule
(Tentative; subject to change.)
• Pset 1 due: Wed of Week 3, 3pm
• Pset 2 due: Wed of Week 5, 3pm
• Pset 3 due: Wed of Week 7, 3pm
• Pset 4 due: Wed of Week 9, 3pm
• Course project
☐ Project proposal due: Wed of Week 6, 3pm
☐ Interim progress report due: Wed of Week 8, 3pm
☐ Final written report due: Wed of Week 10, 3pm
☐ Your peer evaluation report due: Wed of Week 11, 3pm
• Pset 2 due: Wed of Week 5, 3pm
• Pset 3 due: Wed of Week 7, 3pm
• Pset 4 due: Wed of Week 9, 3pm
• Course project
☐ Project proposal due: Wed of Week 6, 3pm
☐ Interim progress report due: Wed of Week 8, 3pm
☐ Final written report due: Wed of Week 10, 3pm
☐ Your peer evaluation report due: Wed of Week 11, 3pm