1/28—Introduction and review

Reading: §1–2

2/2—Approximation algorithms and PCP theorem

Reading: §11

2/9—PCP theorem: gap amplification and hardness of independent set (pdf version)

Reading: §11.2.2, §11.4, §22.2.1

2/11—PCP theorem: hardness of quadratic equations and verifier view (pdf version)

Reading: §11

2/18—PCP theorem: exponential-size proofs (pdf version)

Reading: §11.5

2/23—PCP theorem: local testing and Fourier analysis (pdf version)

Reading: §22.5

2/25—PCP theorem: constraint satisfaction and alphabet reduction

Reading: §22.1, §22.2.1, §22.2.5

3/1—PCP theorem: alphabet reduction

Reading: §22.2.5

3/3—PCP theorem: gap amplification (pdf version)

Reading: §22.2.4

3/8—PCP theorem: gap amplification (pdf version)

Reading: §22.2.4

3/10—PCP theorem: gap amplification (pdf version)

Reading: §22.2.4

3/15—Degree reduction for 2-CSPs via expanders

3/17—Combinatorial vs spectral expansion (pdf version)

Reading: §21.2

3/22—Random walks on expanders

Reading: §21.1

3/24—Zig-zag product (pdf version)

Reading: §21.3

4/5—Explicit expander graph construction

Reading: §21.3

4/7—Randomness efficient error reduction

Reading: §21.2.5

4/12—Deterministic log-space undirected reachability

Reading: §21.4

4/14—Hardness vs randomness overview

4/19—Refutation lower bounds for Random 3SAT

guest lecturer: Samuel B. Hopkins

4/21—Hardness amplification and Impagliazzo’s hardcore lemma (pdf version)

Reading: §19.1

spring break

4/28—Worst case hardness vs average case hardness via local decoding

Reading: §19.4

5/3—Derandomization and pseudorandom generators

Reading: §20.1, guest lecturer: Aaron Potechin

5/5—Pseudorandom generators from hard functions

Reading: §20.2, guest lecturer: Jonathan Shi

5/10—Optimal Inapproximability and 3-bit PCP

Reading: §22.4