Interactive Proofs for General Distributional Properties

This work presents a methodology for verifying whether a claim made by a data analyst (Bob) about an unknown distribution is true, using fewer resources than the data collector (Alice) would need to perform the analysis herself.

In this study, we construct Interactive Proof Systems for general distributional properties decidable by bounded-depth circuits. Letting $N$ denote the support size of the distribution and $D$ the depth of the circuit, the verifier's sample complexity, running time, and communication complexity are all bounded by $\tilde{O}(D + N^{0.99})$.

This system has the following characteristics:

• Doubly-efficient: The honest prover runs in polynomial time and has quasi-linear sample complexity.
• Extensibility: Similar results are shown for properties decidable by bounded-depth Turing machines.
• Distinction from prior work: Unlike previous work, which was limited to the restricted class of 'label-invariant' properties, this study addresses much more general distributional properties.

We note that even for simple properties, determining them directly without a prover requires quasi-linear sample complexity and running time, underscoring the efficiency of this system.