TR07-127 Authors: Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

Publication: 7th December 2007 12:31

Downloads: 1536

Keywords:

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 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$.