CS 254: Computational Complexity

General Information

Instructor: Li-Yang Tan (liyang@cs.stanford.edu)
CAs: Tom Knowles (tknowles@stanford.edu)
         Can Liu (canliu@stanford.edu)
Time: Mondays and Wednesdays, 4:00-5:20pm

Tom's OH: Saturdays 12-1pm
Can's OH: Tuesdays 7-9pm
Homework parties: Mondays 6-8pm


Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.
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
  • If time permits:
    Beyond worst-case complexity
    Hardness within P
    Circuit lower bounds
    Hardness versus randomness
    Barriers to P versus NP

Lecture schedule

(Will be updated as the quarter progresses. Supplementary material listed in gray.)


•  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
Problem set policies:
•  4 late days, at most 2 per pset
•  Late days can only be used for psets, not the project
•  Regrade requests must be submitted within 1 week

Coursework schedule

(Tentative; subject to change.)
•  Pset 1: Jan 27
•  Pset 2: Feb 10
•  Pset 3: Feb 24
•  Pset 4: Mar 8
•  Course project
    ☐ Decide on project topic: Feb 17
    ☐ Interim progress report: Mar 3
    ☐ Final written report: Mar 15
    ☐ Your peer evaluation report: Mar 19