Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PCP Theorem:
TR01-027 | 23rd March 2001
Marius Zimand

Probabilistically Checkable Proofs The Easy Way

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

TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The Power of Unentanglement

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

ISSN 1433-8092 | Imprint