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. On the negative side, we also show that there exist properties for which even a linearly-long (non-interactive) proof of proximity cannot significantly reduce the query complexity.

This revision includes new results in sections 5-7. In section 5, we show that there are properties that, even given a proof of length n/100, still need Omega(n) queries to test by an MAP. In section 6, we consider a class of problems that we call parameterized concatenation problems. These are problems that can be expressed in the form \Pi=\Pi_{\alpha_1} \times ... \times \Pi_{\alpha_k} where \Pi_{\alpha_i} is some property parametrized by \alpha_i. We construct a general MAP for this class of properties and show that it can be used for natural properties. In section 7, we show an MAP for testing bipartiteness of well-mixing graphs in the bounded degree model. The latter two results demonstrate the applicability of MAPs to a wide range of applications.

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.