Marius Zimand

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 >>>

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

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 >>>