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



REPORTS > KEYWORD > 3-QUERY:
Reports tagged with 3-query:
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