Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-062 | 18th April 2013 20:20

An optimal lower bound for monotonicity testing over hypergrids


Authors: C. Seshadhri, Deeparnab Chakrabarty
Publication: 19th April 2013 13:30
Downloads: 3792


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)$.

ISSN 1433-8092 | Imprint