Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INTERACTIVE PROOFS OF PROXIMITY:
Reports tagged with Interactive Proofs of Proximity:
TR22-124 | 9th September 2022
Oded Goldreich, Guy Rothblum, Tal Skverer

On Interactive Proofs of Proximity with Proof-Oblivious Queries

Revisions: 4

Interactive proofs of proximity (IPPs) offer ultra-fast
approximate verification of assertions regarding their input,
where ultra-fast means that only a small portion of the input is read
and approximate verification is analogous to the notion of
approximate decision that underlies property testing.
Specifically, in an IPP, the prover can make ... more >>>


TR24-094 | 19th May 2024
Tal Herman, Guy Rothblum

Interactive Proofs for General Distribution Properties

Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using ... more >>>


TR24-143 | 25th September 2024
Noga Amir, Oded Goldreich, Guy Rothblum

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

1. The query-complexity of verification is significantly smaller than the query-complexity of testing.

2. The query-complexity of the ... more >>>




ISSN 1433-8092 | Imprint