ECCC-Report TR07-127https://eccc.weizmann.ac.il/report/2007/127Comments and Revisions published for TR07-127en-usFri, 07 Dec 2007 12:31:39 +0200
Paper TR07-127
| Sound 3-query PCPPs are Long |
Arie Matsliah,
Eli Ben-Sasson,
Prahladh Harsha,
Oded Lachish
https://eccc.weizmann.ac.il/report/2007/127We 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 proof cannot obtain the
same soundness as that obtained by a verifier querying a long proof.
Moreover, we quantify the {\em soundness deficiency} as a function
of the proof-length and show that any verifier obtaining ``best
possible'' soundness must query an exponentially long proof.
In terms of techniques, we focus on the special class of {\em
inspective} verifiers that read at most $2$ proof-bits per
invocation. For such verifiers we prove {\em exponential}
length-soundness tradeoffs that are later on used to imply our main
results for the case of general (i.e., not necessarily inspective)
verifiers. To prove the exponential tradeoff for inspective
verifiers we show a connection between PCPP proof length and
property-testing query complexity, that may be of independent
interest. The connection is that any property that can be verified
with proofs of length $\ell$ by inspective verifiers must be
testable with query complexity $\approx \log \ell$.
Fri, 07 Dec 2007 12:31:39 +0200https://eccc.weizmann.ac.il/report/2007/127