For positive integers nd , consider the hypergrid [n]d with the coordinate-wise product partial ordering denoted by . A function f:[n]dN is monotone if xy, f(x)f(y).A function f is -far from monotone if at least an -fraction of values must be changed to makef monotone. Given a parameter , a emph{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]dN must make(?1dlogn??1log?1) queries. Recent upper bounds show the existence of O(?1dlogn)query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergridsover arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive boundof (dlogn).
展开▼
