Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids

Research paper by Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Indexed on: 04 Nov '18Published on: 04 Nov '18Published in: arXiv - Computer Science - Discrete Mathematics


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 $\mathbf{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).