Non-interactive proofs of proximity
Non-interactive proofs of proximity
复制标题
非交互式邻近证明
DOI：
--
复制
发表时间：
2015
影响因子：
1.4
通讯作者：
Ron D. Rothblum
中科院分区：
文献类型：
--
作者：
Tom Gur;Ron D. Rothblum
我们启动对这些证明系统的非相互作用证明的研究。它的输入。由于验证者甚至无法读取整个输入，因此拒绝远非有效的输入。被视为$$ {MATHCAL {NP}} $$ NP（或更准确地$$ {MATHCAL {MA}} $ MA）属性测试的类似物。我们表明，此类证明系统可能比财产测试师更强大，但比Rothblum，Vadhan和Wigderson研究的证据证明的互动证明呈指数弱（STOC 2013）。 （几乎）证明的长度与验证者的查询复杂性之间的紧密乘法权衡，我们还表明，现有的属性甚至是线性长（非相互作用）查询复杂性。
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}}$$NP (or more accurately $${mathcal{MA}}$$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.