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 .
For Boolean monotonicity testing over general hypergrids, gave a non-adaptive, one-sided @math -query tester @cite_13 . This was improved to @math by Berman-Raskhodnikova-Yaroslavtsev @cite_21 . They also prove an @math separation between adaptive and non-adaptive monotonicity testers for @math . They show an @math adaptive tester (for any constant @math ), and an @math lower bound for non-adaptive monotonicity testers. Previous work by the authors give a monotonicity tester with query complexity @math via directed isoperimetric inequalities for augmented hypergrids @cite_28 .
@cite_28 @cite_21 @cite_13
2781320126 2593853527 2267350596 2085693797
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 prove a lower bound of Ω(n1 3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f: 0,1 n→ 0,1 is monotone versus far from monotone. This improves the recent lower bound of Ω(n1 4) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs. Beyond monotonicity we prove a lower bound of Ω(√n) for two-sided, adaptive algorithms and a lower bound of Ω(n) for one-sided, non-adaptive algorithms for testing unateness, a natural generalization of monotonicity. The latter matches the linear upper bounds by Khot and Shinkar (RANDOM'16) and by Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri (2017). We show that every algorithm for testing n-variate Boolean functions for monotonicityhas query complexity Ω(n1 4). All previous lower bounds for this problem were designed for non-adaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only Ω(logn). Combined with the query complexity of the non-adaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity. By contrast, we show that there is an exponential gap between the query complexity of adaptive and non-adaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015)recently showed that non-adaptive algorithms require almost Ω(n1 2) queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity O(logn) when the input is a regular LTF. We consider the problem of testing whether an unknown Boolean function f : -- 1, 1 n a#x21C6; -- 1, 1 is monotone versus aepsi;-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an a#x03A9;(n1 5) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function f is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of a#x03A9;(log n) due to [1]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains 1,,m n for all m age; 2. Upper bound: We present an O(n5 6) poly(1 aepsi;)-query algorithm that tests whether an unknown Boolean function f is monotone versus aepsi;-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri[2], which makes O(n7 8) poly(1 aepsi;) queries.