# New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 10 references that are in the map.
- First posted on arXiv 31 Jul 2023.

## Builds on (most cited first, 2 of 2)

- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Shape Restrictions of Discrete Distributions](https://mlsanity.com/paper/1507.03558/) (2015)

## Abstract (arXiv)

We develop a new technique for proving distribution testing lower bounds for properties defined by inequalities involving the bin probabilities of the distribution in question. Using this technique we obtain new lower bounds for monotonicity testing over discrete cubes and tight lower bounds for log-concavity testing. Our basic technique involves constructing a pair of moment-matching families of distributions by tweaking the probabilities of pairs of bins so that one family maintains the defining inequalities while the other violates them.