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