TR13-062 Authors: C. Seshadhri, Deeparnab Chakrabarty

Publication: 19th April 2013 13:30

Downloads: 3193

Keywords:

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) \leq f(y)$.

A function $f$ is $\varepsilon$-far from monotone if at least an $\varepsilon$-fraction of values must be changed to make

$f$ monotone. Given a parameter $\varepsilon$, a \emph{monotonicity tester} must distinguish with high probability a monotone function from one that is $\varepsilon$-far.

We prove that any (adaptive, two-sided) monotonicity tester for functions $f:[n]^d \mapsto \mathbb{N}$ must make

$\Omega(\varepsilon^{-1}d\log n - \varepsilon^{-1}\log \varepsilon^{-1})$ queries. Recent upper bounds show the existence of $O(\varepsilon^{-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)$.