DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.36

Distributed Gaussian Mean Testing Under Communication Constraints: Messages, Samples, and Coins

Authors: Clément L. Canonne and Nimitt

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Clément L. Canonne and Nimitt. Distributed Gaussian Mean Testing Under Communication Constraints: Messages, Samples, and Coins. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2026.36,
  author =	{Canonne, Cl\'{e}ment L. and Nimitt},
  title =	{{Distributed Gaussian Mean Testing Under Communication Constraints: Messages, Samples, and Coins}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.36},
  URN =		{urn:nbn:de:0030-drops-277536},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.36},
  annote =	{Keywords: Distribution Testing, Property Testing, Distributed Algorithms, Communication Constraints}
}

Search Results

Documents authored by Nimitt

Distributed Gaussian Mean Testing Under Communication Constraints: Messages, Samples, and Coins

Abstract

Cite as

Thanks for your feedback!

Could not send message