Communication and Memory Efficient Testing of Discrete Distributions
Abstract
We study distribution testing with communication and memory constraints in the following computational models: (1) The {\em one-pass streaming model} where the goal is to minimize the sample complexity of the protocol subject to a memory constraint, and (2) A {\em distributed model} where the data samples reside at multiple machines and the goal is to minimize the communication cost of the protocol. In both these models, we provide efficient algorithms for uniformity/identity testing (goodness of fit) and closeness testing (two sample testing). Moreover, we show nearly-tight lower bounds on (1) the sample complexity of any one-pass streaming tester for uniformity, subject to the memory constraint, and (2) the communication cost of any uniformity testing protocol, in a restricted “one-pass” model of communication.
Cite
Text
Diakonikolas et al. "Communication and Memory Efficient Testing of Discrete Distributions." Conference on Learning Theory, 2019.Markdown
[Diakonikolas et al. "Communication and Memory Efficient Testing of Discrete Distributions." Conference on Learning Theory, 2019.](https://mlanthology.org/colt/2019/diakonikolas2019colt-communication/)BibTeX
@inproceedings{diakonikolas2019colt-communication,
title = {{Communication and Memory Efficient Testing of Discrete Distributions}},
author = {Diakonikolas, Ilias and Gouleakis, Themis and Kane, Daniel M. and Rao, Sankeerth},
booktitle = {Conference on Learning Theory},
year = {2019},
pages = {1070-1106},
volume = {99},
url = {https://mlanthology.org/colt/2019/diakonikolas2019colt-communication/}
}