Authors
Oded Goldreich, Tom Gur, Ron D Rothblum
Publication date
2018/8/1
Journal
Information and Computation
Volume
261
Pages
175-201
Publisher
Academic Press
Description
Proofs of proximity are proof systems wherein the verifier queries a sublinear number of bits, and soundness only asserts that inputs that are far from valid will be rejected. In their minimal form, called MA proofs of proximity (MAP), the verifier receives, in addition to query access to the input, also free access to a short (sublinear) proof. A more general notion is that of interactive proofs of proximity (IPP), wherein the verifier is allowed to interact with an omniscient, yet untrusted prover. We construct proofs of proximity for two natural classes of properties:(1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are: 1. MAP s for these two classes, in which, for inputs of length n, both the verifier's query complexity and the length of the MAP proof are O˜(n). 2. IPP s for the same two classes with constant query complexity, poly-logarithmic communication complexity …
Total citations
20152016201720182019202020212022202334421332
Scholar articles