Opening Dinur's Proof of the PCP Theorem: The Powering Step
Dinur's Proof of the PCP Theorem: The Powering Step
- Length
- 19 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 2: The powering step definition
CMU 15-750 covers the powering step in Dinur's PCP theorem proof at graduate level. O'Donnell turns length walks into edges, recovers an assignment on the original graph by plurality, and uses the expander mixing lemma to bound violation probabilities.
Your comment is kept while you sign up.Sign in
Details the powering step, the final component of Irit Dinur's proof of the PCP theorem.
CMU 15-750 covers the powering step in Dinur's PCP theorem proof at graduate level. O'Donnell turns length walks into edges, recovers an assignment on the original graph by plurality, and uses the expander mixing lemma to bound violation probabilities.
This lecture
Lecture 89 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. 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.