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 to have run a sophisticated data analysis on the distribution and makes assertions about its properties. When and how is it possible for Alice to efficiently verify Bob’s claims (using fewer resources than would be needed to run the analysis herself)? We construct interactive proof systems for general distribution properties that can be decided by bounded-depth circuits. Taking N to be an upper bound on the distribution’s support size, and D a bound on the depth of a uniform Boolean circuit that gets a complete description of the distribution and decides the property, the verifier’s sample complexity, running time, and the communication complexity are all bounded by Õ(D+N^0.99). The number of rounds is O(D·log(N)). The proof system is doubly-efficient: the honest prover runs in polynomial time and quasi-linear sample complexity. We also show similar results for properties that can be decided by a bounded-depth Turing machine (that gets as input a complete description of the distribution). We remark that even for simple properties, deciding the property without a prover requires quasi-linear sample complexity and running time. Prior work [Herman and Rothblum, FOCS 2023] demonstrated sublinear interactive proof systems, but only for the much more restricted class of label-invariant distribution properties.

• † Weizmann Institute of Science
• ** Work done while at Apple

Related readings and updates.

Doubly Sub-linear Interactive Proofs of Proximity

We study doubly sub-linear interactive proofs of proximity (dsIPPs): proofs that are ultra-fast to generate, and can be used to prove approximate assertions about a huge input. Proof generation is ultra-fast in the sense that it only requires reading a small (sub-linear) portion of the input. Approximate verification of the proof is even faster (reading an even smaller portion of the input). Similarly to the property testing literature,…

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions

As statistical analyses become more central to science, industry and society, there is a growing need to ensure correctness of their results. Approximate correctness can be verified by replicating the entire analysis, but can we verify without replication? Building on a recent line of work, we study proof-systems that allow a probabilistic verifier to ascertain that the results of an analysis are approximately correct, while drawing fewer samples…