We present a weaker variant of the PCP Theorem that admits a
significantly easier proof. In this
variant the prover only has $n^t$ time to compute each
bit of his answer, for an arbitray but fixed constant
$t$, in contrast to
being all powerful. We show that
3SAT ... more >>>

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... more >>>

All known proofs of the PCP theorem rely on multiple "composition" steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy ... more >>>

The original proof of the PCP Theorem composes a Reed-Muller-based PCP with itself, and then composes the resulting PCP with a Hadamard-based PCP [Arora, Lund, Motwani, Sudan and Szegedy ({\em JACM}, 1998)].
Hence, that proof applies a (general) proof composition result twice.
(Dinur's alternative proof consists of logarithmically many gap ... more >>>

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits ... more >>>