We describe a @math -query monotonicity tester for Boolean functions @math on the @math -hypergrid. This is the first @math monotonicity tester with query complexity independent of @math . Motivated by this independence of @math , we initiate the study of monotonicity testing of measurable Boolean functions @math over the continuous domain, where the distance is measured with respect to a product distribution over @math . We give a @math -query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function @math , let @math be its distance to monotonicity. Consider the restriction @math of the function on a random @math sub-hypergrid of the original domain. We show that for @math , the expected distance of the restriction is @math . Previously, such a result was only known for @math (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over @math then follows by applying the @math -query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over @math , we use standard measure theoretic tools to reduce monotonicity testing of a measurable function @math to monotonicity testing of a discretized version of @math over a hypergrid domain @math for large, but finite, @math (that may depend on @math ). The independence of @math in the hypergrid tester is crucial to getting the final tester over @math .
We study monotonicity testing of Boolean functions over the hypergrid [n]d and design a non-adaptive tester with 1-sided error whose query complexity is O(d5 6) · poly(log n, 1 e). Previous to our work, the best known testers had query complexity linear in d but independent of n. We improve upon these testers as long as n = 2do(1). To obtain our results, we work with what we call the augmented hypergrid, which adds extra edges to the hypergrid. Our main technical contribution is a Margulis-style isoperimetric result for the augmented hypergrid, and our tester, like previous testers for the hypercube domain, performs directed random walks on this structure.  We present improved algorithms for testing monotonicity of functions. Namely, given the ability to query an unknown function f: Σ n ↦ Ξ, where Σ and Ξ are finite ordered sets, the test always accepts a monotone f, and rejects f with high probability if it is e-far from being monotone (i.e., every monotone function differs from f on more than an e fraction of the domain). For any e > 0, the query complexity of the test is O((n e) · log ∣Σ ∣ · log ∣Ξ∣). The previous best known bound was ( O ((n^2 ) ^2 ) ).