An Optimal Lower Bound for Monotonicity Testing Over Hypergrids

For positive integers n, d, consider the hypergrid [n] ^d with the coordinate-wise product partial ordering denoted by ≺. A function f: [n] ^d  → ℕ is monotone if ∀ x ≺ y, f(x) ≤ f(y). A function f is ε-far from monotone if at least an ε-fraction of values must be changed to make f monotone. Given a parameter ε, a monotonicity tester must distinguish with high probability a monotone function from one that is ε-far.

We prove that any (adaptive, two-sided) monotonicity tester for functions f:[n] ^d  → ℕ must make Ω(ε ^− 1 dlogn − ε ^− 1logε ^− 1) queries. Recent upper bounds show the existence of O(ε ^− 1 d logn) 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 Ω(d logn).