Theory of Computing
-------------------
Title     : An Optimal Lower Bound for Monotonicity Testing over Hypergrids
Authors   : Deeparnab Chakrabarty and C. Seshadhri
Volume    : 10
Number    : 17
Pages     : 453-464
URL       : https://theoryofcomputing.org/articles/v010a017

Abstract
--------

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 N$ is monotone if $\forall x \prec y$, 
$f(x) \leq f(y)$. A function $f$ is $\epsilon$-far from monotone if 
at least an $\epsilon$ fraction of values must be changed to make 
$f$ monotone. Given a parameter $\epsilon$, a _monotonicity tester_ 
must distinguish with high probability a monotone function from 
one that is $\epsilon$-far.

We prove that any (adaptive, two-sided) monotonicity tester for
functions $f:[n]^d \to N$ must make $\Omega(\epsilon^{-1}d\log n -
\epsilon^{-1}\log \epsilon^{-1})$ queries. Recent upper bounds show the
existence of $O(\epsilon^{-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).