# Collision-based Testers are Optimal for Uniformity and Closeness

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2016.

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

- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [On Differentially Private U Statistics](https://mlsanity.com/paper/2407.04945/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)
- [Testing with Non-identically Distributed Samples](https://mlsanity.com/paper/2311.11194/) (2023)
- [Instance-Optimal Uniformity Testing and Tracking](https://mlsanity.com/paper/2508.02637/) (2025)
- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)
- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)
- [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026)
- [Differentially Private Verification of Distribution Properties](https://mlsanity.com/paper/2604.10819/) (2026)
- [When Are Trade-Off Functions Testable from Finite Samples?](https://mlsanity.com/paper/2605.10774/) (2026)
- [One-Shot Private Confidence Regions via Resampling](https://mlsanity.com/paper/2610.08460/) (2026)

## Abstract (arXiv)

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 ε.