Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids

الأصل · EN

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given query access to f:[k]ⁿ (for some ordered range). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by. A function is monotone if for all pairs x y, f(x) ≤ f(y). The distance to monotonicity,, 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(⁻¹n||) samples can distinguish a monotone function from one where >. On the other hand, the best lower bound for monotonicity testing over the hypercube is (||²,n). This leaves a quadratic gap in our knowledge, since || can be 2ⁿ. We resolve this long standing open problem and prove that O(n/) samples suffice for the edge tester. For hypergrids, known testers require O(⁻¹n k ||) samples, while the best known (non-adaptive) lower bound is Ω(⁻¹ n k). We give a (non-adaptive) monotonicity tester for hypergrids running in O(⁻¹ n k) time. Our techniques lead to optimal property testers (with the same running time) for the natural Lipschitz property on hypercubes and hypergrids. (A c-Lipschitz function is one where |f(x) - f(y)| ≤ cx-y₁.) In fact, we give a general unified proof for O(⁻¹n k)-query testers for a class of "bounded-derivative" properties, a class containing both monotonicity and Lipschitz.