Interactive Proofs and the PCP Theorem
Stub. From graph isomorphism (a natural problem with an interactive zero-knowledge-flavored proof) to interactive proofs in general, and on to the PCP theorem: every NP statement has a proof that can be checked by reading only a constant number of (randomly chosen) bits, with the Hadamard-code-based PCP as the concrete construction — and why this is equivalent to hardness of approximation for optimization problems.
Corresponds to advanced course, Lectures 7–9 (partial). Graph nonisomorphism has no obvious short certificate, yet admits a simple interactive proof (challenge the prover to tell which of two possibly- relabeled graphs a random one came from), which is the motivating example for interactive proofs as a generalization of NP — see advanced-topics-in-classical-complexity for the IP = PSPACE theorem this generalization leads to classically, and zero-knowledge-proofs for the cryptographic use of the same model. The PCP theorem is the far more striking statement that NP proofs can be rewritten so a randomized verifier reads only bits of the (polynomially longer) rewritten proof and still catches any error with constant probability — constructed concretely here via the Hadamard code (a proof format robust enough that local corruption can’t hide a wrong answer). The theorem’s equivalent restatement — approximating many NP-hard optimization problems within certain factors is itself NP-hard — is what makes it a cornerstone of hardness-of-approximation theory, not just a proof-system curiosity.
Outline (TODO — flesh out each)
- From graph isomorphism to interactive proofs
- Randomness, verification, and hardness of approximation
- The PCP theorem — statement
- Probabilistically checkable proofs via the Hadamard code