Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-061 | 14th August 2000 00:00

Small PCPs with low query complexity

RSS-Feed




TR00-061
Authors: Prahladh Harsha, Madhu Sudan
Publication: 24th August 2000 15:14
Downloads: 1530
Keywords: 


Abstract:

Most known constructions of probabilistically checkable proofs (PCPs)
either blow up the proof size by a large polynomial, or have a high
(though constant) query complexity. In this paper we give a
transformation with slightly-super-cubic blowup in proof size, with a
low query complexity. Specifically, the verifier probes the proof in
16 bits and rejects every proof of a false assertion with probability
arbitrarily close to half, while accepting corrects proofs of
theorems with probability one. The proof is obtained by revisiting
known constructions and improving numerous components therein. In the
process we abstract a number of new modules that may be of use in
other PCP constructions.



ISSN 1433-8092 | Imprint