Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-127 | 22nd November 2007 00:00

Sound 3-query PCPPs are Long


Authors: Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish
Publication: 7th December 2007 12:31
Downloads: 1427


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

ISSN 1433-8092 | Imprint