Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with distribution testing, property testing:
TR22-052 | 18th April 2022
Tal Herman, Guy Rothblum

Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties

Given i.i.d. samples from an unknown distribution over a large domain $[N]$, approximating several basic quantities, including the distribution's support size, its entropy, and its distance from the uniform distribution, requires $\Theta(N / \log N)$ samples [Valiant and Valiant, STOC 2011].

Suppose, however, that we can interact with a powerful ... 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