Doubly Sub-linear Interactive Proofs of Proximity

Webpage for a paper by Noga Amir, Oded Goldreich, and Guy Rothblum

Abstract

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which

The query-complexity of verification is significantly smaller than the query-complexity of testing.
The query-complexity of the honest prover strategy is not much larger than the query-complexity of testing.

We call such proof systems doubly-sublinear IPPs (dsIPPs). We present a few doubly-sublinear IPPs. A salient feature of these IPPs is that the honest prover does not employ an optimal strategy. In particular, the honest prover in our IPP for sets recognizable by constant-width read-once oblivious branching programs uses a distance-approximator for such sets.

Material available on-line

First version posted: Sept 2024.
Revisions: none yet.

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