Simpler Distribution Testing with Little Memory
arXiv:2311.01145
Abstract
We consider the question of distribution testing (specifically, uniformity and closeness testing) in the streaming setting, \ie under stringent memory constraints. We improve on the results of Diakonikolas, Gouleakis, Kane, and Rao (2019) by providing considerably simpler algorithms, which remove some restrictions on the range of parameters and match their lower bounds.
To appear in the 2024 SIAM Symposium on Simplicity in Algorithms (SOSA'24)