# Optimal Algorithms for Testing Closeness of Discrete Distributions

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2013.

## Built on by (most cited first, 30 of 37)

- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Byzantine-Robust Online and Offline Distributed Reinforcement Learning](https://mlsanity.com/paper/2206.00165/) (2022)
- [An Auditing Test To Detect Behavioral Shift in Language Models](https://mlsanity.com/paper/2410.19406/) (2024)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits](https://mlsanity.com/paper/2110.04253/) (2021)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Uniformity Testing over Hypergrids with Subcube Conditioning](https://mlsanity.com/paper/2302.09013/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Bias Detection via Maximum Subgroup Discrepancy](https://mlsanity.com/paper/2502.02221/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Total Variation Distance Estimation in Autoregressive Models](https://mlsanity.com/paper/2607.19510/) (2026)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)
- [Mathematical Framework for Online Social Media Auditing](https://mlsanity.com/paper/2209.05550/) (2022)
- [Testing High-dimensional Multinomials with Applications to Text Analysis](https://mlsanity.com/paper/2301.01381/) (2023)
- [Testing with Non-identically Distributed Samples](https://mlsanity.com/paper/2311.11194/) (2023)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Instance-Optimal Uniformity Testing and Tracking](https://mlsanity.com/paper/2508.02637/) (2025)
- [Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions](https://mlsanity.com/paper/2603.04635/) (2026)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testing](https://mlsanity.com/paper/2110.06325/) (2021)
- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)
- [Membership Testing in Markov Equivalence Classes via Independence Query Oracles](https://mlsanity.com/paper/2403.05759/) (2024)
- [Testing Credibility of Public and Private Surveys through the Lens of Regression](https://mlsanity.com/paper/2410.05458/) (2024)

## Abstract (arXiv)

We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions p and q over an n-element set, we wish to distinguish whether p=q versus p is at least eps-far from q, in either ℓ1 or ℓ2 distance. Batu et al. gave the first sub-linear time algorithms for these problems, which matched the lower bounds of Valiant up to a logarithmic factor in n, and a polynomial factor of eps. In this work, we present simple (and new) testers for both the ℓ1 and ℓ2 settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on n, and the dependence on eps; for the ℓ1 testing problem we establish that the sample complexity is Theta(maxn2/3/eps4/3, n1/2/eps2 ).