Revised: December 3, 2014
Published: December 24, 2014
Abstract: [Plain Text Version]
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 \NN is monotone if \forall 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 \to \NN must make \Omega(\eps^{-1}d\log 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 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).