Doubly Sub-linear Interactive Proofs of Proximity

We study doubly sub-linear interactive proofs of proximity (dsIPPs): proofs that are ultra-fast to generate, and can be used to prove approximate assertions about a huge input. Proof generation is ultra-fast in the sense that it only requires reading a small (sub-linear) portion of the input. Approximate verification of the proof is even faster (reading an even smaller portion of the input). Similarly to the property testing literature, approximate verification means the sublinear-time honest prover can make the verifier accept each input in the property, but no prover can fool the verifier into accepting an input that is far from the property. Such proof systems can be used to prove (and verify) claims about the properties of a huge input object, even though the prover cannot read the entire object (and the verifier is even more restricted). We construct such a proof system for any property that can be decided by a constant-width read-once oblivious branching program (ROOBP). We also construct proof systems for approximate verification of an input’s Hamming weight, and for a relaxation of bipartiteness in the bounded-degree graph model.

• † Weizmann Institute