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

Webpage for a paper by Oded Goldreich, Tom Gur, and Ron Rothblum


Proofs of proximity are probabilistic proof systems in which the verifier only queries a \emph{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:

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.