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 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).  The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube 1,l,m n. These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2-CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest. We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes, up to polylog factors, (square root of n) a#x03B5;2 non-adaptive queries to a function f:0, 1n -> 0, 1, always accepts a monotone function and rejects a function that is a#x03B5;-far from being monotone with constant probability.  A Boolean function @math is said to be @math -far from monotone if @math needs to be modified in at least @math -fraction of the points to make it monotone. We design a randomized tester that is given oracle access to @math and an input parameter @math and has the following guarantee: It outputs Yes if the function is monotonically nondecreasing and outputs No with probability @math , if the function is @math -far from monotone. This nonadaptive, one-sided tester makes @math queries to the oracle. 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.  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.