2026-09-10T09:45:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27753 2026-09-09T12:19:36Z ddc:004 open_access

Distributed Gaussian Mean Testing Under Communication Constraints: Messages, Samples, and Coins Canonne, Clément L. Nimitt Distribution Testing Property Testing Distributed Algorithms Communication Constraints We revisit the problem of Gaussian mean testing in a distributed, communication constrained setting, where each of n users independently observes samples from an unknown d-dimensional spherical Gaussian distribution 𝒢(μ,𝕀_d), and can communicate up to 𝓁 bits to a central referee. The referee’s goal is then to distinguish between cases (i) ‖μ‖₂ = 0 versus (ii) ‖μ‖₂ ≥ ε. This problem has been considered in the private- and public-coin settings, when each user holds exactly one sample, or more generally when each holds exactly m samples. In this work, we significantly generalize the question in three directions: when the users only share a small number s of random bits, when each user holds a different number of samples m_k, and when each user can send a different number of bits 𝓁_k to the referee. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Nimitt 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.36 urn:nbn:de:0030-drops-277536 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.36 eng https://creativecommons.org/licenses/by/4.0/legalcode