# An optimal lower bound for monotonicity testing over hypergrids

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2013.

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

- [Uniformity Testing over Hypergrids with Subcube Conditioning](https://mlsanity.com/paper/2302.09013/) (2023)
- [Monotone Classification with Relative Approximations](https://mlsanity.com/paper/2506.10775/) (2025)

## Abstract (arXiv)

For positive integers n, d, consider the hypergrid [n]d with the coordinate-wise product partial ordering denoted by prec. A function f: [n]d mapsto mathbbN is monotone if forall x prec y, f(x) ≤ f(y). A function f is eps-far from monotone if at least an eps-fraction of values must be changed to make f monotone. Given a parameter eps, a monotonicity tester must distinguish with high probability a monotone function from one that is eps-far. We prove that any (adaptive, two-sided) monotonicity tester for functions f:[n]d mapsto mathbbN must make Omega(eps-1dlog n - eps-1log eps-1) queries. Recent upper bounds show the existence of O(eps-1d log n) query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of Omega(d log n).