Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions in $d$-Dimensions

We describe a $tilde{O}(d^{5/6})$-query monotonicity tester for Boolean functions $f:[n]^d to {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:mathbb{R}^d to {0,1}$ over the continuous domain, where the distance is measured with respect to a product distribution over $mathbb{R}^d$. We give a $tilde{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 to {0,1}$, let $epsilon_f$ be its distance to monotonicity. Consider the restriction $hat{f}$ of the function on a random $[k]^d$ sub-hypergrid of the original domain. We show that for $k = text{poly}(d/epsilon)$, the expected distance of the restriction is $mathbb{E}[epsilon_{hat{f}}] = Omega(epsilon_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}cdot text{poly}(1/epsilon,log n, log d)$-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over $mathbb{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 $mathbb{R}^d$.