Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

ISSN 1433-8092 | Imprint