An optimal lower bound for monotonicity testing over hypergrids

Abstract

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 \mathbb{N}$ is monotone if $\forall x\prec y$, $f(x)\le 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 \emph{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 \mathbb{N}$ must make $Ω(\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)$.