Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TRANSPARENT PROOFS:
Reports tagged with Transparent proofs:
TR00-061 | 14th August 2000
Prahladh Harsha, Madhu Sudan

Small PCPs with low query complexity

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




ISSN 1433-8092 | Imprint