Statement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory Toolkit @RyanODonnellTeaching
Statement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory Toolkit  @RyanODonnellTeaching
Uploaded July 2020 | Updated November 2026, 1 day ago
Remarks about the PCP Theorem, Dinur's proof of it, and a full statement of the theorem, including its hardness-of-approximation interpretation and its proof-checking interpretation. Lecture 27a 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, https://courses.cs.washington.edu/courses/cse533/05au/

Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)

Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/

Thumbnail photo by Rebecca Kiger (rebeccakphoto.com/)
Statement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory Toolkit#36/100: Toggle and Hadamard are reflections || Quantum Computer Programming in 100 Easy Lessons#90/100: Verifying the first SW vector properties | Quantum Computer Programming in 100 Easy LessonsETH False II: completing the proofPseudorandom Generators || @ CMU || Lecture 12a of CS Theory ToolkitImproved Quantum Data Analysis (Shadow Tomography)Learning About Quantum States 4:  The Schur Weyl Distribution#66/100: Factoring via Rotation Estimation: plan || Quantum Computer Programming in 100 Easy LessonsExpander Graphs Overview || @ CMU || Lecture 16a of CS Theory ToolkitThe Ellipsoid Algorithm || @ CMU || Lecture 19a of CS Theory Toolkit#23/100: AND/OR/NOT code (for CCode → QCode) || Quantum Computer Programming in 100 Easy LessonsLearning About Quantum States 8:  Learning the eigenvectors via GL(d) representation theory
Ryan ODonnell |

Statement of the PCP Theorem || @ CMU || Lecture 27a of CS Theory Toolkit

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER