Optimal bounds for monotonicity and Lipschitz testing over the hypercube
Deeparnab Chakrabarty, Comandur Seshadhri · arXiv (Cornell University) · 2012
The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved question in property testing. We are given query access to f : {0, 1} 7→ R (for some ordered range R). The boolean hypercube B has a natural partial order, denoted by ≺ (defined by the product of coordinate-wise ordering). A function is monotone if all pairs x ≺ y in B, f(x) ≤ f(y). The distance to monotonicity, ef , is the minimum fraction of values of f that need to be changed to make f monotone. It is known that the edge tester using O(n log |R|/e) samples can distinguish a monotone function from one where ef > e. On the other hand, the best lower bound for monotonicity testing is min(|R|, n). This leaves a quadratic gap in our knowledge, since |R| can be 2. We prove that the edge tester only requires O(n/e) samples (regardless of R), resolving this question. Our technique is quite general, and we get optimal edge testers for the Lipschitz property. We prove a very general theorem showing that edge testers work for a class of “bounded-derivative” properties, which contains both monotonicity and Lipschitz.