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

(

$${\mathcal {MAP}}$$

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

(

$${\mathcal {IPP}}$$

IPP

), in which the verifier is allowed to interact with an all-powerful, yet untrusted, prover.

$${\mathcal {MAP}}$$

MAP

s and

$${\mathcal {IPP}}$$

IPP

s may be thought of as the

$${\mathcal {NP}}$$

NP

and

$${\mathcal {IP}}$$

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.

$${\mathcal {MAP}}$$

MAP

s for these two classes, in which, for inputs of length

$$n$$

n

, both the verifier’s query complexity and the length of the

$${\mathcal {MAP}}$$

MAP

proof are

$$\widetilde{O}(\sqrt{n})$$

O

~

(

n

)

.

2.

$${\mathcal {IPP}}$$

IPP

s for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.