The Library
Non-interactive proofs of proximity
Tools
Gur, Tom and Rothblum, Ron D. (2018) Non-interactive proofs of proximity. Computational Complexity, 27 (1). pp. 99-207. doi:10.1007/s00037-016-0136-9 ISSN 1016-3328.
|
PDF
WRAP-non-interactive-proofs-proximity-Gur-2018.pdf - Accepted Version - Requires a PDF viewer. Download (2334Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00037-016-0136-9
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 N P (or more accurately 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Probabilities | ||||||||
Journal or Publication Title: | Computational Complexity | ||||||||
Publisher: | Springer | ||||||||
ISSN: | 1016-3328 | ||||||||
Official Date: | March 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 27 | ||||||||
Number: | 1 | ||||||||
Page Range: | pp. 99-207 | ||||||||
DOI: | 10.1007/s00037-016-0136-9 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Reuse Statement (publisher, data, author rights): | This is a post-peer-review, pre-copyedit version of an article published in Computational Complexity. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00037-016-0136-9 | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 12 February 2019 | ||||||||
Date of first compliant Open Access: | 13 February 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year