CS 254B: Computational Complexity II

General Information

Instructor: Li-Yang Tan (liyang@cs.stanford.edu)
Time: Mondays and Wednesdays 4:30-5:50pm
Office hours: Thursdays 1:30-3:30pm

Course Outline

  • Part I
    Baker-Gill-Solovay: The relativization barrier
    Hopcroft-Paul-Valiant: On time versus space
    Ladner's theorem and NP-intermediate problems
    Time-space tradeoffs for SAT
  • Part II
    Nisan-Wigderson pseudorandom generators
    Hardness amplification via Yao's XOR lemma
    Impagliazzo's hardcore set lemma
    Dualities between hardness amplification and boosting
  • Part III
    Beyond worst-case analysis
    Hardness within P
    SAT algorithms and the Exponential Time Hypothesis
  • Part IV
    Expander graphs
    Unconditional derandomization
    Analysis of Boolean functions
  • Part V
    Broader perspectives on complexity theory: A discussion
    Li-Yang's research; Ask Me Anything
    Project presentations


•  Project presentation. Due Monday June 8, 4:30pm
•  Project report. Due Wednesday June 10, 4:30pm
•  Peer evaluation. Due Wednesday June 10, 4:30pm