mlsanityData to 7 Oct 2026

Optimal Algorithms for Testing Closeness of Discrete Distributions

arXiv 1308.3946 ↗First posted 19 Aug 2013cs.DS cs.IT cs.LGcited by 37

Not on the map. Why?

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

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 6; 2024: 6; 2025: 7; 2026: 5.

37 papers.

Sort:

  1. 2021Exponential separations between learning with and without quantum memorycited by 50
  2. 2021The Price of Tolerance in Distribution Testingcited by 13
  3. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  4. 2023Testing Closeness of Multivariate Distributions via Ramsey Theorycited by 8
  5. 2024An Auditing Test To Detect Behavioral Shift in Language Modelscited by 8
  6. 2021Robust Testing and Estimation under Manipulation Attackscited by 5
  7. 2022Near-Optimal Bounds for Testing Histogram Distributionscited by 4
  8. 2022Complexity of High-Dimensional Identity Testing with Coordinate Conditional Samplingcited by 4
  9. 2024Replicable Uniformity Testingcited by 4
  10. 2021F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuitscited by 3
  11. 2022Gaussian Mean Testing Made Simplecited by 3
  12. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
25 more
  1. 2022Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimationcited by 2
  2. 2023Uniformity Testing over Hypergrids with Subcube Conditioningcited by 2
  3. 2024Optimal Algorithms for Augmented Testing of Discrete Distributionscited by 2
  4. 2025Bias Detection via Maximum Subgroup Discrepancycited by 2
  5. 2025Replicable Distribution Testingcited by 2
  6. 2022Sharp Constants in Uniformity Testing via the Huber Statisticcited by 1
  7. 2022Mathematical Framework for Online Social Media Auditingcited by 1
  8. 2023Testing High-dimensional Multinomials with Applications to Text Analysiscited by 1
  9. 2023Testing with Non-identically Distributed Samplescited by 1
  10. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  11. 2025Instance-Optimal Uniformity Testing and Trackingcited by 1
  12. 2026Optimal Prediction-Augmented Algorithms for Testing Independence of Distributionscited by 1
  13. 2026Total Variation Distance Estimation in Autoregressive Modelscited by 1
  14. 2021Uniformity Testing in the Shuffle Model: Simpler, Better, Fastercited by 0
  15. 2021As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testingcited by 0
  16. 2023The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternativescited by 0
  17. 2024Membership Testing in Markov Equivalence Classes via Independence Query Oraclescited by 0
  18. 2024Testing Credibility of Public and Private Surveys through the Lens of Regressioncited by 0
  19. 2025Optimal structure learning and conditional independence testingcited by 0
  20. 2025Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approachcited by 0
  21. 2025Non-iid hypothesis testing: from classical to quantumcited by 0
  22. 2025A Distribution Testing Approach to Clustering Distributionscited by 0
  23. 2026When Are Trade-Off Functions Testable from Finite Samples?cited by 0
  24. 2026Entropy Equivalence Testingcited by 0
  25. 2026The Oversight Gap: What LLM Safety Monitors Miss, and Why It Is Not Capabilitycited by 0