ECCC-Report TR13-062https://eccc.weizmann.ac.il/report/2013/062Comments and Revisions published for TR13-062en-usFri, 19 Apr 2013 13:30:55 +0300
Paper TR13-062
| An optimal lower bound for monotonicity testing over hypergrids |
C. Seshadhri,
Deeparnab Chakrabarty
https://eccc.weizmann.ac.il/report/2013/062For 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)$. Fri, 19 Apr 2013 13:30:55 +0300https://eccc.weizmann.ac.il/report/2013/062