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



REPORTS > KEYWORD > PROOF-LENGTH:
Reports tagged with proof-length:
TR07-127 | 22nd November 2007
Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

Sound 3-query PCPPs are Long

We initiate the study of the tradeoff between the {\em length} of a probabilistically checkable proof of proximity (PCPP) and the maximal {\em soundness} that can be guaranteed by a $3$-query verifier with oracle access to the proof. Our main observation is that a verifier limited to querying a short ... more >>>



ISSN 1433-8092 | Imprint