Opening Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP
Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP
- Length
- 26 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Degree reduction step
The three more 'standard' parts of Irit Dinur's proof of the PCP Theorem (though there are innovations in these steps, too): degree-reduction, expanderizing, and alphabet-reduction (AKA composition with a constant-size PCPP). Lecture 27c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture Course on "The PCP Theorem and Hardness of Approximation" by O'Donnell and Guruswami
Course homepage on CMU's Diderot system

Your comment is kept while you sign up.Sign in
Details degree-reduction, expanderizing, and mini-PCP steps in Dinur's PCP Theorem proof via expander graphs.
The three more 'standard' parts of Irit Dinur's proof of the PCP Theorem (though there are innovations in these steps, too): degree-reduction, expanderizing, and alphabet-reduction (AKA composition with a constant-size PCPP). Lecture 27c of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.
Resource for this lecture Course on "The PCP Theorem and Hardness of Approximation" by O'Donnell and Guruswami
Course homepage on CMU's Diderot system
Dinur's paper
This lecture
Lecture 88 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.