# 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 '18**Published on: **04 Nov '18**Published in: **arXiv - Computer Science - Discrete Mathematics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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).