# Testing Identity of Structured Distributions

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

## Key facts

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

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

- [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)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (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)
- [Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation](https://mlsanity.com/paper/2502.05730/) (2025)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Testing with Non-identically Distributed Samples](https://mlsanity.com/paper/2311.11194/) (2023)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [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)
- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)
- [Near-optimal algorithms for private estimation and sequential testing of collision probability](https://mlsanity.com/paper/2504.13804/) (2025)
- [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

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