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 : http://www.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).