Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
share
We describe a Õ(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 Õ(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/ϵ, n, 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.
READ FULL TEXT