# Testing Shape Restrictions of Discrete Distributions

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2015.

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

- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Testing properties of distributions in the streaming model](https://mlsanity.com/paper/2309.03245/) (2023)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions](https://mlsanity.com/paper/2603.04635/) (2026)
- [As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testing](https://mlsanity.com/paper/2110.06325/) (2021)
- [New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions](https://mlsanity.com/paper/2308.00089/) (2023)
- [Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more](https://mlsanity.com/paper/2606.11469/) (2026)

## Abstract (arXiv)

We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution D over [n] and a property P, the goal is to distinguish between D∈P and ℓ1(D,P)>varepsilon. We develop a general algorithm for this question, which applies to a large range of "shape-constrained" properties, including monotone, log-concave, t-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly-tight upper and lower bounds for the corresponding questions.