Previous slide Next slide Back to the first slide View text 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