2026-07-26T00:47:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22634 2026-04-17T05:31:38Z ddc:004 open_access

Doubly Sub-Linear Interactive Proofs of Proximity Amir, Noga Goldreich, Oded Rothblum, Guy N. Interactive Proof Systems Interactive Proofs of Proximity Query Complexity Read Once Branching Programs Sub-linear 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 1) The query-complexity of verification is significantly smaller than the query-complexity of testing. 2) 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 (i.e. a strategy that maximizes the verifier’s acceptance probability). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noga Amir and Oded Goldreich and Guy N. Rothblum 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.6 urn:nbn:de:0030-drops-226345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.6 eng https://creativecommons.org/licenses/by/4.0/legalcode