mlsanityData to 14 Oct 2026

Testing Identity of Structured Distributions

arXiv 1410.2266 ↗First posted 8 Oct 2014cs.DS cs.IT math.ITcited by 19

Not on the map. Why?

Abstract (arXiv)

We study the question of identity testing for structured distributions. More precisely, given samples from a em structured distribution q over [n] and an explicit distribution p over [n], we wish to distinguish whether q=p versus q is at least ε-far from p, in L1 distance. In this work, we present a unified approach that yields new, simple testers, with sample complexity that is information-theoretically optimal, for broad classes of structured distributions, including t-flat distributions, t-modal distributions, log-concave distributions, monotone hazard rate (MHR) distributions, and mixtures thereof.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 Oct 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 2; 2023: 5; 2024: 2; 2025: 3; 2026: 4.

19 papers.

Sort:

  1. 2021Exponential separations between learning with and without quantum memorycited by 52
  2. 2021The Price of Tolerance in Distribution Testingcited by 14
  3. 2023Testing Closeness of Multivariate Distributions via Ramsey Theorycited by 8
  4. 2022Near-Optimal Bounds for Testing Histogram Distributionscited by 4
  5. 2024Replicable Uniformity Testingcited by 4
  6. 2022Gaussian Mean Testing Made Simplecited by 3
  7. 2023Uniformity Testing over Hypergrids with Subcube Conditioningcited by 2
  8. 2024Optimal Algorithms for Augmented Testing of Discrete Distributionscited by 2
  9. 2025Attainability of Two-Point Testing Rates for Finite-Sample Location Estimationcited by 2
  10. 2025Replicable Distribution Testingcited by 2
  11. 2023Testing with Non-identically Distributed Samplescited by 1
  12. 2023Statistical Inference with Limited Memory: A Surveycited by 1
7 more
  1. 2026Optimal Prediction-Augmented Algorithms for Testing Independence of Distributionscited by 1
  2. 2021Uniformity Testing in the Shuffle Model: Simpler, Better, Fastercited by 0
  3. 2023The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternativescited by 0
  4. 2025Near-optimal algorithms for private estimation and sequential testing of collision probabilitycited by 0
  5. 2026Relatively Smart: A New Approach for Instance-Optimal Learningcited by 0
  6. 2026Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and morecited by 0
  7. 2026Testing Distributions Against Bounded Distinguisherscited by 0