Crash Course on Probabilistically Checkable Proofs (PCP)...

on YouTube ↗01h 18m

" summary

Gives a constructive weak PCP: map any system of quadratic mod‑2 equations E to a huge Ẽ where each new equation touches only three bits, E satisfiable implies Ẽ satisfiable, and if E is unsatisfiable then at least a constant (≈0.01) fraction of Ẽ fails. The verifier samples a random equation in polynomial time and runs four 1/4 tests (two linearity checks, a product consistency check, and a self‑correction check); the construction is exponential size but each sampled check is efficient and the scheme underlies practical verifiers.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:45PCP Theorem
3. 5:00Global Properties
4. 9:00Can PCP be formulated in P language
5. 15:00Global vs Local Tests
6. 15:45Computational Problem
7. 24:12Simple Construction
8. 26:45Construction
9. 28:45Linear Functions
10. 29:45Variables
11. 30:45Equations
12. 52:45Conclusion
13. 56:45Proof