Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

Abstract

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic question in property testing. We are given query access to f:[k]n -> R (for some ordered range R). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by prec. A function is monotone if for all pairs x prec y, f(x) ≤ f(y). The distance to monotonicity, εf, is the minimum fraction of values of f that need to be changed to make f monotone. For k=2 (the boolean hypercube), the usual tester is the edge tester, which checks monotonicity on adjacent pairs of domain points. It is known that the edge tester using O(ε-1n log|R|) samples can distinguish a monotone function from one where εf > ε. On the other hand, the best lower bound for monotonicity testing over general R is Ω(n). We resolve this long standing open problem and prove that O(n/ε) samples suffice for the edge tester. For hypergrids, known testers require O(ε-1n log k log |R|) samples, while the best known (non-adaptive) lower bound is Ω(ε-1 n log k). We give a (non-adaptive) monotonicity tester for hypergrids running in O(ε{-1} n log k) time.