Domain Reduction for Monotonicity Testing: A o ( d ) Tester for Boolean Functions on Hypergrids

摘要

We describe a O ( d 5 6 ) -query monotonicity tester for Boolean functions f : [ n ] d 0 1 on the n -hypergrid. This is the first o ( d ) monotonicity tester with query complexity independent of n . Motivated by this independence of n , we initiate the study of monotonicity testing of measurable Boolean functions f : R d 0 1 over the continuous domain, where the distance is measured with respect to a product distribution over R d . We give a O ( d 5 6 ) -query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function f : [ n ] d 0 1 , let f be its distance to monotonicity. Consider the restriction f of the function on a random [ k ] d sub-hypergrid of the original domain. We show that for k = poly ( d ) , the expected distance of the restriction is E [ f ] = ( f ) . Previously, such a result was only known for d = 1 (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over [ n ] d then follows by applying the d 5 6 poly (1 log n log d ) -query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over R d , we use standard measure theoretic tools to reduce monotonicity testing of a measurable function f to monotonicity testing of a discretized version of f over a hypergrid domain [ N ] d for large, but finite, N (that may depend on f ). The independence of N in the hypergrid tester is crucial to getting the final tester over R d .