Dinur's PCP- Degree-Reduction, Expanderizing, Mini-PCP - Lecture 27c of CS Theory Toolkit

Explore the three standard components of Irit Dinur's proof of the PCP Theorem in this graduate-level lecture from Carnegie Mellon University's "CS Theory Toolkit" course. Delve into degree-reduction, expanderizing, and alphabet-reduction (also known as composition with a constant-size PCPP), while noting the innovative approaches within these steps. Learn from Professor Ryan O'Donnell as he breaks down these complex concepts, drawing from resources like the "The PCP Theorem and Hardness of Approximation" course. Gain valuable insights into fundamental mathematics and computer science principles essential for research in theoretical computer science. Access additional course materials through CMU's Diderot system to further enhance your understanding of this advanced topic.

Intro
Degree Reduction
White and Yellow edges
Expanders
MiniPCP
How to miniPCP