CS 254B: Computational Complexity II
General Information
Instructor: Li-Yang Tan
Time: Mondays and Wednesdays 3-4:20pm
CA: Caleb Koch
Caleb's OH: TBD
Li-Yang's OH: After class by appointment
Time: Mondays and Wednesdays 3-4:20pm
CA: Caleb Koch
Caleb's OH: TBD
Li-Yang's OH: After class by appointment
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
Lecture schedule
(Will be updated as the quarter progresses. Supplementary material listed in gray.)
- Lecture 1: Course overview
- Lecture 2: The relativization barrier
Relativizations of the P versus NP Question, Baker, Gill, and Solovay
- Lectures 3 and 4: On time versus space
On time versus space, Hopcroft, Paul, and Valiant
Space bounds for a game on graphs, Paul, Tarjan, and Celoni - Lectures 5 and 6: Time-space tradeoffs for SAT
- Lecture 7: Ladner's theorem
- Lecture 8: Overview of Hardness vs. Randomness
Chapter 7 of Mathematics and Computation, Wigderson
- Lectures 9 to 11: PRGs from Average-Case Hardness
Hardness vs randomness, Nisan and Wigderson
- Lectures 12 and 13: Hardness amplification
On Yao’s XOR-Lemma, Goldreich, Nisan, and Wigderson
- Lectures 14 and 15: Beyond worst-case analysis
- Lecture 16: Hardness within P
- Lecture 17: Research talk
- Lecture 18: Research talk
- Lecture 19: AMA
Evaluation
(Tentative; more details to follow.)
• 70%: Course project: report, presentation, peer evaluation
☐ Interim progress report (5%)
☐ Final written report (25%)
☐ Video presentation (25%)
☐ Peer evaluation (15%)
• 30%: High-quality scribe and elaboration of 1 lecture
• CR: All project components except interim and final reports
☐ Interim progress report (5%)
☐ Final written report (25%)
☐ Video presentation (25%)
☐ Peer evaluation (15%)
• 30%: High-quality scribe and elaboration of 1 lecture
• CR: All project components except interim and final reports
Coursework schedule
(Tentative; subject to change.)
• Scribe notes
☐ Due 1 week after the lecture at 3pm
• Course project
☐ Project proposal due Wed of Week 6 at 3pm
☐ Interim progress report due Wed of Week 8 at 3pm
☐ 20-minute video due Wed of Week 10 at 3pm
☐ Project report due Wed of Week 10 at 3pm
☐ Peer evaluation due Wed of Week 11 at 3pm
☐ Due 1 week after the lecture at 3pm
• Course project
☐ Project proposal due Wed of Week 6 at 3pm
☐ Interim progress report due Wed of Week 8 at 3pm
☐ 20-minute video due Wed of Week 10 at 3pm
☐ Project report due Wed of Week 10 at 3pm
☐ Peer evaluation due Wed of Week 11 at 3pm