2016/11/11 by Ilias Diakonikolas, Themis Gouleakis, Diakonikolas, Ilias +5 · 5 citations
Computer Science · Medicine · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #SARS-CoV-2 detection and testing #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1611.03579
openalex publication_date 2016/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded ℓ2-norm. These problems have been extensively studied in distribution testing and sample-optimal estimators are known for them~\citePaninski:08, CDVV14, VV14, DKN:15. In this work, we show that the original collision-based testers proposed for these problems ~\citeGRdist:00, BFR+:00 are sample-optimal, up to constant factors. Previous analyses showed sample complexity upper bounds for these testers that are optimal as a function of the domain size n, but suboptimal by polynomial factors in the error parameter ε. Our main contribution is a new tight analysis establishing that these collision-based testers are information-theoretically optimal, up to constant factors, both in the dependence on n and in the dependence on ε.