CS 254: Computational Complexity

General Information

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.

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


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


•  4 problem sets (70%)
•  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
•  Regrade requests must be submitted within 1 week

A few project reports

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