We describe a \tilde{O}(d^{5/6})-query monotonicity tester for Boolean functions f \colon [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 \colon \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\colon[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_f), 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.

We describe a \tilde{O}(d^{5/6})-query monotonicity
tester for Boolean functions f \colon [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\colon\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 \emph{domain reduction theorem}
for monotonicity. For any function f\colon[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_f), 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.

Testing monotonicity of Boolean functions over the hypergrid, f:[n]^d \to \{0,1\}, is a classic problem in property testing. When the range is real-valued, there are \Theta(d\log n)-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of n: There are testers with query complexity independent of n [Dodis et al. (RANDOM 1999); Berman et al. (STOC 2014)], with linear dependence on d.
(2) Sublinear in d: For the n=2 hypercube case, there are testers with o(d) query complexity [Chakrabarty, Seshadhri (STOC 2013); Khot et al. (FOCS 2015)].
It was open whether one could obtain both properties simultaneously. This paper answers this question in the affirmative. We describe a \tilde{O}(d^{5/6})-query monotonicity tester for f:[n]^d \to \{0,1\}.
Our main technical result is a domain reduction theorem for monotonicity. For any function f, 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 \mathbb{E}[\epsilon_{\hat{f}}] = \Omega(\epsilon_f). Therefore, for monotonicity testing in d dimensions, we can restrict to testing over [n]^d, where n = \text{poly}(d/\epsilon). Our result 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).

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.

Testing monotonicity of Boolean functions over the hypergrid, f:[n]^d \to \{0,1\}, is a classic problem in property testing. When the range is real-valued, there are \Theta(d\log n)-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of n: There are testers with query complexity independent of n [Dodis et al. (RANDOM 1999); Berman et al. (STOC 2014)], with linear dependence on d.
(2) Sublinear in d: For the n=2 hypercube case, there are testers with o(d) query complexity [Chakrabarty, Seshadhri (STOC 2013); Khot et al. (FOCS 2015)].
It was open whether one could obtain both properties simultaneously. This paper answers this question in the affirmative. We describe a \tilde{O}(d^{5/6})-query monotonicity tester for f:[n]^d \to \{0,1\}.
Our main technical result is a domain reduction theorem for monotonicity. For any function f, 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 \mathbb{E}[\epsilon_{\hat{f}}] = \Omega(\epsilon_f). Therefore, for monotonicity testing in d dimensions, we can restrict to testing over [n]^d, where n = \text{poly}(d/\epsilon). Our result 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).