Noga Amir

Abstract of Master Thesis (Weizmann Inst., 2024)

Doubly Sub-linear Interactive Proofs of Proximity


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

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.


Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, Oct 2024.

Available: the thesis (in PDF file).


Back to Oded Goldreich's homepage.