# Communication and Memory Efficient Testing of Discrete Distributions

arXiv: https://arxiv.org/abs/1906.04709 · HTML: https://mlsanity.com/paper/1906.04709/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2019.

## Built on by (most cited first, 8 of 8)

- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Strong Memory Lower Bounds for Learning Natural Models](https://mlsanity.com/paper/2206.04743/) (2022)
- [On Differential Privacy and Adaptive Data Analysis with Bounded Space](https://mlsanity.com/paper/2302.05707/) (2023)
- [Estimation of Entropy in Constant Space with Improved Sample Complexity](https://mlsanity.com/paper/2205.09804/) (2022)
- [Testing properties of distributions in the streaming model](https://mlsanity.com/paper/2309.03245/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026)

## Abstract (arXiv)

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.