ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > PROBABILISITIC CHECKING OF PROOFS (PCP):
Reports tagged with probabilisitic checking of proofs (PCP):
TR98-008 | 15th January 1998
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

Proof verification and the hardness of approximation problems.

We show that every language in NP has a probablistic verifier
that checks membership proofs for it using
logarithmic number of random bits and by examining a
<em> constant </em> number of bits in the proof.
If a string is in the language, then there exists a proof
more >>>


TR98-034 | 23rd June 1998
Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

A tight characterization of NP with 3 query PCPs

It is known that there exists a PCP characterization of NP
where the verifier makes 3 queries and has a {\em one-sided}
error that is bounded away from 1; and also that 2 queries
do not suffice for such a characterization. Thus PCPs with
3 queries ... more >>>


TR98-040 | 24th July 1998
Madhu Sudan, Luca Trevisan

Probabilistically checkable proofs with low amortized query complexity

The error probability of Probabilistically Checkable Proof (PCP)
systems can be made exponentially small in the number of queries
by using sequential repetition. In this paper we are interested
in determining the precise rate at which the error goes down in
an optimal protocol, and we make substantial progress toward ... more >>>




ISSN 1433-8092 | Imprint