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
- 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.
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.