Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-321 | 19th November 2026 17:03

The Communication Complexity of Verifying Distribution Properties

RSS-Feed




TR26-321
Authors: Tal Herman
Publication: 19th November 2026 17:10
Downloads: 15
Keywords: 


Abstract:

Suppose an untrusted powerful data analyst collected many samples from an unknown distribution, and claims that the distribution satisfies some property. For example, that it is close to uniform, or has large support. Can they provide a convincing proof to this effect? If so, what is the complexity of certifying this proof? Is it possible to be convinced of its correctness with fewer resources than required for the original computation?

A recent line of work shows that indeed many fundamental claims about distributions admit proof systems with an efficient verifier that draws only a few samples from the distribution. While the question of the optimal sample complexity required for such proofs has received much attention, their communication complexity remained essentially unaddressed, besides in the limited public-coin regime. In this work we give the first communication complexity lower bounds for general proofs for distributions, including secret-coin protocols and computationally sound systems with efficient honest provers, that apply to natural distribution properties.

We show a lower bound on the number of bits required for verifying fundamental quantities of a distribution, including its Shannon entropy, its distance from uniform, and its support size under a minimum-probability promise. For nearly optimal verifier sample complexity, we complement these lower bounds with matching communication upper bounds on the hard families, up to polylogarithmic factors and polynomial dependence on accuracy, using two-message proof systems with nearly optimal verifier and honest-prover sample complexity.

Our lower bound result reveals a connection between interactive proofs for distributions and fundamental problems in communication complexity.



ISSN 1433-8092 | Imprint