2018/11/04 by Black, Hadley, Chakrabarty, Deeparnab, Seshadhri, C.
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1811.01427
We describe a O(d5/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:ℝd → \0,1\ over the continuous domain, where the distance is measured with respect to a product distribution over ℝd. We give a O(d5/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 𝔼[ε_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 d5/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 ℝ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 ℝd.