| Previous slide | Next slide | Back to the first slide | View Graphic Version |
PCP - prover commits to long proof that verifier can spot check randomly. Invented by Arora and Safra
Proof complicated - uses multilinear testing combined with special error correcting codes.
Applications to optimization problems, particularly MAXSNP class of Papadimitriou and Yannakakis