Interactive Proofs for General Distribution Properties

Details

This FOCS 2026 paper by Tal Herman and Guy Rothblum (Apple ML Research / Weizmann Institute) addresses a core problem in statistical auditing: can Alice verify Bob's data analysis claims using far fewer resources than it would take to replicate the analysis? The paper constructs interactive proof systems for general distribution properties — specifically, any property decidable by a bounded-depth Boolean circuit that takes a complete description of the distribution. For a distribution with support size N and a circuit of depth D, the verifier's sample complexity, running time, and communication cost are all bounded by Õ(D+N^0.99). The number of protocol rounds is O(D·log(N)). The honest prover runs in polynomial time with quasi-linear sample complexity, making this a doubly-efficient proof system. The result significantly extends prior work. Herman and Rothblum's 2023 FOCS paper demonstrated sublinear interactive proofs only for label-invariant (symmetric) distribution properties — those that depend only on value frequencies, not positions. The new paper generalizes to arbitrary bounded-depth-circuit-decidable properties. Practical relevance is forward-looking: as AI systems increasingly make decisions from statistical claims about datasets users cannot inspect, efficient verification protocols become relevant for audits and compliance. The gap to practical implementation is large — the theoretical setting assumes an honest prover with specific polynomial-time capabilities.