Opening Statement of the PCP Theorem
Statement of the PCP Theorem
- Length
- 14 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Before the lecture
The PCP theorem says it is NP-hard to tell a perfectly three-colorable graph from one where every coloring violates an fraction of edges. O'Donnell opens with the history of the early-1990s proofs and Dinur's much shorter 2005 proof. He then defines badness as the minimum fraction of violated constraints in a constraint satisfaction problem instance. The theorem becomes a polynomial-time reduction from circuit-SAT to max three-coloring, trading plain satisfiability for hardness of approximation. Recast as a probabilistically checkable proof, the statement lets a verifier trust a huge proof after spot-checking a constant number of vertices, with closing remarks on cryptographic uses.

Your comment is kept while you sign up.Sign in
Frames the PCP theorem as a reduction from circuit-SAT to max three-coloring with a constant gap.
The PCP theorem says it is NP-hard to tell a perfectly three-colorable graph from one where every coloring violates an fraction of edges. O'Donnell opens with the history of the early-1990s proofs and Dinur's much shorter 2005 proof. He then defines badness as the minimum fraction of violated constraints in a constraint satisfaction problem instance. The theorem becomes a polynomial-time reduction from circuit-SAT to max three-coloring, trading plain satisfiability for hardness of approximation. Recast as a probabilistically checkable proof, the statement lets a verifier trust a huge proof after spot-checking a constant number of vertices, with closing remarks on cryptographic uses.
Paper by Irit Dinur
This lecture
Lecture 86 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.