Sound 3-Query PCPPs Are Long

DOI DOI Open Access

Search this article

Description

<jats:p>We initiate the study of the trade-off between the length of a probabilistically checkable proof of proximity (PCPP) and the maximal 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 soundness deficiency as a function of the proof-length and show that any verifier obtaining “best possible” soundness must query an exponentially long proof.</jats:p> <jats:p> In terms of techniques, we focus on the special class of inspective verifiers that read at most 2 proof-bits per invocation. For such verifiers, we prove <jats:italic>exponential</jats:italic> length-soundness trade-offs 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 trade-off 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 linear property that can be verified with proofs of length ℓ by linear inspective verifiers must be testable with query complexity ≈ logℓ. </jats:p>

Journal

Details 詳細情報について

Report a problem

Back to top