CS 254B: Computational Complexity II

General Information

Instructor: Li-Yang Tan
Time: Mondays and Wednesdays 3:15-4:45pm
CA: Victor Lecomte

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

Evaluation

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

Coursework schedule

(Tentative; subject to change.)
•  Scribe notes
    ☐ First draft due: 1 week after the lecture
    ☐ Final version due: 1 week after Victor's feedback

•  Course project
    ☐ Project proposal due: Wed of Week 6, 3pm
    ☐ Interim progress report due: Wed of Week 8, 3pm
    ☐ 20-minute video due: Wed of Week 10, 3pm
    ☐ Project report due: Wed of Week 11, 5pm
    ☐ Peer evaluation due: Wed of Week 11, 5pm