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 >>>
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 >>>
Suppose that an untrusted analyst claims that it ran a distribution tester and determined that an unknown distribution has a certain property. Can the untrusted analyst prove that its assertion is correct to a verifier that does not have sufficient samples and computational resources to run the tester on its ... more >>>
Suppose an untrusted powerful data analyst collected many samples from an unknown distribution, and claims that the distribution satisfies some property. For example, that it is close to uniform, or has large support. Can they provide a convincing proof to this effect? If so, what is the complexity of certifying ... more >>>