Opening Dinur's Proof of the PCP Theorem: Outline
Dinur's Proof of the PCP Theorem: Outline
- Length
- 29 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Equivalence of CSP reductions
Dinur's proof of the PCP theorem recasts it as a badness amplification theorem for constraint satisfaction problems, starting from graph 3-coloring. O'Donnell first notes that 3-coloring, 3-SAT and other NP-hard CSPs reduce to one another. The goal is a polynomial-time reduction that doubles the fraction of violated constraints with only constant size blowup. The reduction has four steps: degree-reduce brings the graph to constant degree, expanderize adds spectral expansion, and powering doubles badness using a large label set and high-degree paths. A final mini-PCP step restores the 3-coloring format, and iterating the whole reduction logarithmically many times yields the theorem. Part of CMU 15-750, A Theorist's Toolkit (lecture 27b); assumes NP-completeness, basic graph theory and CSPs.

Your comment is kept while you sign up.Sign in
O'Donnell splits Dinur's gap amplification into degree-reduce, expanderize, power and mini-PCP, doubling badness.
Dinur's proof of the PCP theorem recasts it as a badness amplification theorem for constraint satisfaction problems, starting from graph 3-coloring. O'Donnell first notes that 3-coloring, 3-SAT and other NP-hard CSPs reduce to one another. The goal is a polynomial-time reduction that doubles the fraction of violated constraints with only constant size blowup. The reduction has four steps: degree-reduce brings the graph to constant degree, expanderize adds spectral expansion, and powering doubles badness using a large label set and high-degree paths. A final mini-PCP step restores the 3-coloring format, and iterating the whole reduction logarithmically many times yields the theorem. Part of CMU 15-750, A Theorist's Toolkit (lecture 27b); assumes NP-completeness, basic graph theory and CSPs.
This lecture
Lecture 87 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.