Simpler Distribution Testing with Little Memory

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.

Machine Learning and Algorithms Machine Learning and Data Classification Bayesian Methods and Mixture Models

Paper

Similar papers

Simpler Distribution Testing with Little MemoryClément L. Canonne, Joy Qiping Yang2024 · Society for Industrial and Applied Mathematics eBooks In Library

Testing properties of distributions in the streaming modelSampriti Roy, Yadu Vasudev2023 · arXiv (Cornell University) In Library

On The Memory Complexity of Uniformity TestingTomer Berg, Or Ordentlich, Ofer Shayevitz2022 · arXiv (Cornell University) In Library

Uniformity Testing in the Shuffle Model: Simpler, Better, FasterClément L. Canonne, Hongyi Lyu2021 · arXiv (Cornell University) In Library

Uniformity Testing in the Shuffle Model: Simpler, Better, FasterClément L. Canonne, Hongyi Lyu2022 · Society for Industrial and Applied Mathematics eBooks In Library

Distribution Testing Under the Parity TraceRenato Ferreira Pinto, Nathaniel Harms2023 · arXiv (Cornell University) In Library

Replicable Uniformity TestingSihan Liu, Christopher Ye2024 · Neural Information Processing Systems · 4 citations In Library

Testing Properties of Multiple Distributions with Few SamplesMaryam Aliakbarpour, Sandeep Silwal2020 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

Distribution Testing with a Confused CollectorRenato Ferreira Pinto, Nathaniel Harms2023 · arXiv (Cornell University) In Library

Testing with Non-identically Distributed SamplesShivam Garg, Chirag Pabbaraju, Kirankumar Shiragur et al.2023 · arXiv (Cornell University) In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal