An Optimal Lower Bound for Monotonicity Testing over Hypergrids

摘要

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 o NN$ is monotone if $orall x prec y$, $f(x) leq f(y)$.A function $f$ is $eps$-far from monotone if at least an $eps$ fraction of values must be changed to make$f$ monotone. Given a parameter $eps$, a monotonicity tester must distinguish with high probability a monotone function from one that is $eps$-far.We prove that any (adaptive, two-sided) monotonicity tester for functions $f:[n]^d o NN$ must make$Omega(eps^{-1}dlog n - eps^{-1}log eps^{-1})$ queries. Recent upper bounds show the existence of $O(eps^{-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 boundof $Omega(d log n)$. A conference version of this paper appeared in the Proceedings of the 17th Internat. Workshop o Randomizationand Computation (RANDOM 2013).