CS 254: Computational Complexity

Instructor: Li-Yang Tan (liyang@cs.stanford.edu)
CA: Emma Zhong (emmazjy@stanford.edu)
Classroom: Gates B12
Time: Mondays and Wednesdays, 4:30-5:50pm

Emma's OH: Tuesdays 1-3pm (Gates B26)
Li-Yang's OH: Fridays 4:15-6:15pm (Gates 466)

Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
Mathematics and Computation, by Avi Wigderson.

• 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
• If time permits:
  Beyond worst-case complexity
  Hardness within P
  Circuit lower bounds
  Hardness versus randomness
  Barriers to P versus NP
  ...

• Jan 7: Course overview; the grand challenges of complexity theory
• Jan 9: CS154 recap
  Chapters 20.2, 3.4, and 20.4 of Wigderson's book
• Jan 14: Space complexity; Savitch's theorem
• Jan 16: Non-deterministic logspace; STCONN is NL-complete
  The complexity of graph connectivity, Avi Wigderson
  Undirected connectivity in log-space, Omer Reingold
• Jan 23: Immerman-Szelepcsényi theorem
  1995 Gödel prize citation
• Jan 28: NP, coNP, and NP ∩ coNP
  Chapters 3.5 and 6 of Wigderson's book
  Gödel's 1956 letter to von Neumann
  Propositional proof complexity: past, present, and future, Paul Beame and Toniann Pitassi
  The limits of proof, video of a talk by Paul Beame
  
• Jan 30: The polynomial hierarchy
• Feb 4: P^SAT and oracle Turing machines
• Feb 6: The power of randomness in computation
  Chapter 7 of Wigderson's book
  Finding hay in haystacks: the power and limits of randomness, video of a talk by Avi Wigderson
  Pseudorandomness, monograph by Salil Vadhan
• Feb 11: Randomized complexity. P versus BPP; NP versus BPP
• Feb 13: A glimpse of hardness vs randomness and explicit construction of Ramsey graphs
  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
  
• Feb 20: Non-uniform computation and circuit complexity
  Chapter 5 of Wigderson's book
  P =? NP, Scott Aaronson
  Some estimated likelihoods for computational complexity, Ryan Williams
  
• Feb 25: Relating P/poly to BPP and NP: Adelman's theorem and the Karp-Lipton theorem
• Feb 27: Interactive proofs
  Chapter 10 of Wigderson's book
  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
• March 4: Interactive proof for #3SAT
• March 6: Arthur and Merlin
  Proof positive? Throw dinner parties with statistical confidence, Larry Gonick
• March 11: Goldwasser-Sipser AM protocol for approximate counting
• March 13: Unique-SAT and the Valiant-Vazirani theorem

•  4 problem sets (70%)
•  Course project (30%)
    ☐ Interim progress report (5%)
    ☐ Final written report (15%)
    ☐ Your peer evaluation report (10%)
•  In-class participation (+5%)

•  4 late days, at most 2 per pset
•  Regrade requests must be submitted within 1 week

The natural proofs barrier and P =? NP
On the computational intractability of cryptographic systems
Undirected connectivity is in L: an overview of the proof
Formal barriers to proving P ≠ NP: relativization and natural proofs
Fractional pseudorandom generators
Quantum computation and complexity
Pseudorandomness: applications to cryptography and derandomization
Derandomization from hardness
Hardness vs. randomness
Hitting set generators: a different lens into P vs. BPP
The oracle separation of BQP and PH
Computational complexity and philosophy