CS 254B: Computational Complexity II

General Information

Instructor: Li-Yang Tan
Time: Mondays and Wednesdays 4:00-5:20pm
CA: Tom Knowles

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
    Impagliazzo-Wigderson theorem
    Dualities between hardness amplification and boosting
  • Part III
    Beyond worst-case analysis
    Hardness within P
    SAT algorithms; the Exponential Time Hypothesis and its variants
  • Part IV
    Expander graphs
    Derandomization techniques
    Fourier analysis of Boolean functions
  • Part V
    Broader perspectives on complexity theory: A discussion
    Li-Yang's research; Ask Me Anything
    Project presentations


(Tentative; more details to follow.)
•  Course project: report, presentation, peer evaluation
•  High-quality scribe and elaboration of 1 lecture