Non-Interactive Proofs of Proximity

by Tom Gur and Ron Rothblum

Oded's comments

This new model of a probabilistic proof systems may be vieved in several ways. The first way is as a special case of interactive proofs of proximity (see Choice Nr. 109); that is, the case of unidirectional communication from the prover to the verifier, who only probes the main input (via oracle access). The second way is as the missing part in a taxonomy of non-interactive proof systems, which is spanned by whether the input and/or the proof are presented explicitly or via an oracle: In the current work, the input is presented via an oracle (like in property testing), whereas the proof is presented explicitly (like in NP). Recall that PCP refers to explicit input and oracle access to the proof, whereas PCPP refers to the case that the verifier only has oracle access to both the input and the proof.

Either way, the focus is on short proofs, and the question is whether such short (non-interactive) proofs may significantly reduce the complexity of (property) testing. The work contains several results that address this question.

The original abstract

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire input, we only require it to reject inputs that are far from being valid. Thus, the verifier is only assured of the proximity of the statement to a correct one. Such proof-systems can be viewed as the $\mathcal{NP}$ (or more accurately $\mathcal{MA}$) analogue of property testing.

We explore both the power and limitations of non-interactive proofs of proximity. We show that such proof-systems can be exponentially stronger than property testers, but are exponentially weaker than the interactive proofs of proximity studied by Rothblum, Vadhan and Wigderson (STOC 2013). In addition, we show a natural problem that has a full and (almost) tight multiplicative trade-off between the length of the proof and the verifier's query complexity.

See ECCC TR13-078.


Back to list of Oded's choices.