Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs (Extended Abstract)
Oded Goldreich, Tom Gur, Ron D. Rothblum · Apollo (University of Cambridge) · 2015
Proofs of proximity are probabilistic proof systems in which the verifier only queries a sublinear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input.In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition to query access to the input, also free access to an explicitly given short (sub-linear) proof.A more general notion is that of an interactive proof of proximity (IPP), in which the verifier is allowed to interact with an all-powerful, yet untrusted, prover.MAPs and IPPs may be thought of as the N P and IP analogues of property testing, respectively.In this work 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. MAPs 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. IPPs for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.