Proofs of proximity are probabilistic proof systems in which the verifier only queries a
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
), 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
), in which the verifier is allowed to interact with an all-powerful, yet untrusted, prover.
s may be thought of as the
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:
s for these two classes, in which, for inputs of length
, both the verifier’s query complexity and the length of the
s for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.