Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs∗

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear 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 NP 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 Õ(√n). 2. IPPs for the same two classes with constant query complexity, poly-logarithmic commu