Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Probabilistically Checkable Proofs (PCP):
TR96-047 | 2nd September 1996
Oded Goldreich, Muli Safra

A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))
is very complicated.
One source of difficulty is the technically involved
analysis of low-degree tests.
Here, we refer to the difficulty of obtaining strong results
regarding low-degree tests; namely, results of the type obtained and
used by ... more >>>

TR05-014 | 30th January 2005
Oded Goldreich

Short Locally Testable Codes and Proofs (Survey)

We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the ... more >>>

ISSN 1433-8092 | Imprint