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 Θ(N / logN) samples [Valiant and Valiant, STOC 2011].