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