CS 254B: Computational Complexity II
General Information
Instructor: Li-Yang Tan (liyang@cs.stanford.edu)
Time: Mondays and Wednesdays 4:30-5:50pm
Office hours: Thursdays 1:30-3:30pm
Time: Mondays and Wednesdays 4:30-5:50pm
Office hours: Thursdays 1:30-3:30pm
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
Dualities between hardness amplification and boosting - Part III
Beyond worst-case analysis
Hardness within P
SAT algorithms and the Exponential Time Hypothesis - Part IV
Expander graphs
Unconditional derandomization
Analysis of Boolean functions - Part V
Broader perspectives on complexity theory: A discussion
Li-Yang's research; Ask Me Anything
Project presentations
Evaluation
• Project presentation. Due Monday June 8, 4:30pm
• Project report. Due Wednesday June 10, 4:30pm
• Peer evaluation. Due Wednesday June 10, 4:30pm
• Project report. Due Wednesday June 10, 4:30pm
• Peer evaluation. Due Wednesday June 10, 4:30pm