__
TR24-141 | 12th September 2024 09:50
__

#### Public Coin Interactive Proofs for Label-Invariant Distribution Properties

TR24-141
Authors:

Tal Herman
Publication: 12th September 2024 11:38

Downloads: 111

Keywords:

**Abstract:**
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$.