Under the auspices of the Computational Complexity Foundation (CCF)

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