CS 254: Computational Complexity

General Information

Instructor: Li-Yang Tan (liyang@cs.stanford.edu)
CAs: Ray Li (rayyli@stanford.edu)
         William Marshall (wfm@stanford.edu)
Classroom: Gates B12
Time: Mondays and Wednesdays, 4:30-5:50pm

Ray's OH: Mondays 9-11am (B26)
William's OH: Tuesdays 12:45-2:45pm (B26)
Li-Yang's OH: Thursdays 1:30-3:30pm (Gates 466)


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%)
•  In-class participation (+5%)
In-class discussions will be an important component of this course, and hence attendance will be expected.

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: due Jan 22
•  Pset 2: due Feb 5
•  Pset 3: due Feb 19
•  Pset 4: due March 4
•  Course project
    ☐ Decide on project topic: Feb 12
    ☐ Interim progress report: Due Feb 26
    ☐ Final written report: Due March 11
    ☐ Your peer evaluation report: Due March 20