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 → N is monotone if (A)_x (λ) y, f(x) ≤ f(y). A function / is e-far from monotone if at least an e-fraction of values must be changed to make / monotone. Given a parameter e, 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 → N must make Ω(ε~(~1)d log n - ε~(-l) logeε~(-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 log n).