CS 254B: Computational Complexity II
General Information
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.)
• Course project: report, presentation, peer evaluation
• High-quality scribe and elaboration of 1 lecture
• High-quality scribe and elaboration of 1 lecture