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.)
• 70%: Course project: report, presentation, peer evaluation
• 30%: High-quality scribe and elaboration of 1 lecture
• 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
☐ 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