Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with soundness:
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