Distributed Uniformity Testing

By Orr Fischer, Uri Meir, Rotem Oshman. 2018

15 citations recorded by the source corpus.

In the uniformity testing problem, we are given access to samples from some unknown distribution μ on a fixed domain \set1,..,n , and our goal is to distinguish the case where μ is the uniform distribution from the case where μ is ε-far from uniform in L_1 distance. Centralized uniformity testing has been extensively studied, and it is known that Θ(√ /ε^2) samples are necessary and sufficient. In this paper we study distributed uniformity testing : in a network of k nodes, each node i has access to s_i samples from the underlying distribution μ. Our goal is to test uniformity, while minimizing the number of samples per node, as well as the running time. We consider several distributed models: the ŁOCAL model, the \CONGEST model, and a 0-round model where nodes cannot communicate with each other at all. We give upper bounds for each model, and a lower bound for the 0-round model. The key to our results is analyzing the centralized uniformity-testing problem in an unusual error regime, for which we give new upper and lower bounds.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, background): “(2019c,b), as well as by (with a slightly different focus) (Fischer et al., 2018).”
Communication and Memory Efficient Testing of Discrete Distributions (2019, methodology): “We remind the reader that testing uniformity based on the number of pairwise collisions is the oldest algorithm in distribution testing Goldreich and Ron (2000), which is now known to be sample-optimal in the centralized setting Diakonikolas et al.”
Distributed Signal Detection under Communication Constraints (2020, background): “…Xu and Raginsky, 2017; Han et al., 2018a,b; Barnes et al., 2019; Cai and Wei, 2020; Acharya et al., 2019b,d), while distributed testing of distributions in the ﬁnite sample regime was considered in (Acharya et al., 2019b,d; Andoni et al., 2018; Fischer et al., 2018; Diakonikolas et al., 2019).”