Abstract: Independent draws from a $d$-dimensional spherical Gaussian distribution are distributed across users, each holding one sample. A central server seeks to distinguish between the two hypotheses: the distribution has zero mean, or the mean has $\ell_2$-norm at least $\varepsilon$, a pre-specified threshold. However, the users can each transmit at most $\ell$ bits to the server. This is a distributed variant of the classic problem of detecting signal in white noise.\n\nWe study this distributed testing problem with and without the availability of a common randomness shared by the users. We design schemes with and without such shared randomness. We then obtain lower bounds for protocols with public randomness, which are tight when $\ell=O(1)$. We finally conclude with several conjectures and open problems.

Summary presentation

Full presentation