Revised: December 3, 2014

Published: December 24, 2014

**Keywords:**lower bounds, property testing, monotonicity testing

**ACM Classification:**K.4.1, I.2.6, F.2.0

**AMS Classification:**68Q32, 68Q25, 68W20

**Abstract:**
[Plain Text Version]

For positive integers $n, d$, the hypergrid $[n]^d$ is equipped with the
coordinatewise product partial ordering denoted by $\prec$.
A function $f: [n]^d \to \NN$ is monotone if
$\forall x \prec y$, $f(x) \leq 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 \to \NN$ must make $\Omega(\eps^{-1}d\log n - \eps^{-1}\log \eps^{-1})$ queries. Recent upper bounds show the existence of $O(\eps^{-1}d \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)$.

A conference version of this paper appeared in the Proceedings of the 17th Internat. Workshop o Randomization and Computation (RANDOM 2013).