Crash Course on Probabilistically Checkable Proofs (PCP): Introduction
Talkat Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020) · 2020-08-19..08-28
summary
Crash-course claim: NP languages admit a randomized verifier that reads O(1) proof bits after tossing O(log n) coins, so a polynomial-time reduction maps any instance G to G̃ where satisfiable instances stay satisfiable and unsatisfiable ones become far from satisfiable (value ≤ 0.99). Consequences: NP-hardness of approximating Max‑3‑Coloring to that gap, Håstad’s tight constants for 3‑LIN (≈1/2), and proof techniques built from reductions, parallel repetition and the long‑code gadget.
AI-written summary · about