Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

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(ε -1 n 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(ε -1 n 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.

Authors

• Deeparnab Chakrabarty
• C. Seshadhri 0001

Keywords

• hypercubes
• property testing
• monotonicity
• lipschitz testing
• hypergrids