Simpler Distribution Testing with Little Memory

2023/11/02 by Clément L. Canonne, Canonne, Clément L., Joy Qiping Yang +1 · 1 voice · 1 citation
Computer Science · #Bayesian Methods and Mixture Models #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #Machine Learning and Data Classification #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.2311.01145

openalex publication_date 2023/11/02 · arxiv published 2023/11/02 · arxiv updated 2023/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Multi-Pass Streaming Lower Bounds for Uniformity Testing

Discussions

• New paper, with my PhD student Joy Yang at U Syd: "Simpler Distribution Testing with Little Memory", to appear at #SOSA24. We give simpler algorithms for uniformity/closeness testing in the streaming [bsky, 3 points, 0 comments]

Related

• Communication and Memory Efficient Testing of Discrete Distributions
• Testing properties of distributions in the streaming model
• Multi-Pass Streaming Lower Bounds for Uniformity Testing
• Testing frequency distributions in a stream
• Testing Properties of Multiple Distributions with Few Samples