Assume we are given sample access to an unknown distribution $D$ over a large domain $[N]$. An emerging line of work has demonstrated that many basic quantities relating to the distribution, such as its distance from uniform and its Shannon entropy, despite being hard to approximate through the samples only, can be {\em efficiently and verifiably} approximated through interaction with an untrusted powerful prover, that {\em knows} the entire distribution [Herman and Rothblum, STOC 2022, FOCS 2023]. Concretely, these works provide an efficient proof system for approximation of any label-invariant distribution quantity (i.e. any function over the distribution that's invariant to a re-labeling of the domain $[N]$).

In our main result, we present the first efficient {\em public coin} AM protocol, for any label-invariant property. Our protocol achieves sample complexity and communication complexity of magnitude $\widetilde{O}(N^{2/3})$, while the proof can be generated in quasi-linear $\widetilde{O}(N)$ time.

On top of that, we also give a public-coin protocol for efficiently verifying the distance a between a samplable distribution $D$, and some explicitly given distribution $Q$.