Transcript Probabilistically Checkable Proofs What Theoretical Computer

Probabilistically Checkable Proofs
What Theoretical Computer Science
Discovered About Proofs
Dana Moshkovitz
The Institute For Advanced Study
My Reflections About Theoretical
Computer Science and Mathematics
Algebra
Mathematics
Analysis
Probability
Logic
Combinatorics
Mathematical Proofs
Checkability!
1. P0
2. P0 → (P1 → P2)
3. P1 → P2
4. …
Mathematical Proofs
Checkability!
Checking
Algorithm
Y/N
The Probabilistically Checkable Proofs
Theorem [BFLS,AS,ALMSS, 1992]
The PCP Theorem: Every proof can be efficiently
converted to a proof that can be checked
probabilistically by querying only two symbols
in the proof.
Probabilistic Checking of Proofs
Checking algorithm V  Checking algorithm V’
V’ makes two probabilistic queries to its proof!
• Completeness: A proof  that satisfies V can be
efficiently converted to a proof ‘ that V’ accepts
with probability 1.
• Soundness: If V’ accepts a proof ‘ with
probability >, then there exists a proof  that
satisfies V.
Remark: ‘ over alphabet  where||1/.
Should We Referee This Way?
PCP Theorem
!?
Almost-linear
conversion!
[GS02,BSVW03,BGHSV04,
BS05,D06,MR07,MR08]
Completely
formal proof
Locally testable
proof
Theoretical Computer Science Angle:
Hardness of Approximation
Big Open Problem in Theoretical Computer
Science until 1991: Show that some
approximation problem is NP-hard.
1991-2: The PCP Theorem resolves this!
The approximation problem: Approximate
how many of the checker’s local tests can
be satisfied simultaneously.
What Gets Inside?
• Low degree testing Low degree approximations and
restrictions to lines/planes in Fqn
[RS90,…,AS97,RS97,MR06]
• Combinatorial PCP Random walks on expanders [D06]
• Parallel repetition Information theory [R94,H07]
• Parallel repetition tightness Foam Tiling of Rn by Zn
[R08,FKO07,KORW08]
• Long-Code testing Isoperimetric inequalities in
Gaussian space [KKMO04,MOO05]
• UGC-based reductions Counterexamples for metric
embedding [KV05,…]
Research on PCP Today
• Realization: The type of check matters!
– Projection games
– Unique games
• Biggest open problems:
– “The Sliding-Scale Conjecture” smallest possible error
(n)=1/n [BGLR93,AS97,RS97,DFKRS99,MR07]
• for projection games [R94,MR08]
– “The Unique Games Conjecture” arbitrarily small
constant error for unique games [K02]
• More open problems: minimize size, alphabet,
conversion time, checking time, more hardness of
approximation results, more connections…