A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

Abstract

Monotonicity testing of Boolean functions on the hypergrid, $f:[n{]}^d\to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $n$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\tilde{O}({\epsilon }^{-4/3}{d}^{5/6})$. This complexity is independent of $n$, but has a suboptimal dependence on $d$. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $\tilde{O}({\epsilon }^{-2}{n}^3\sqrt{d})$ and $\tilde{O}({\epsilon }^{-2}n\sqrt{d})$-query testers, respectively. These testers have an almost optimal dependence on $d$, but a suboptimal polynomial dependence on $n$. In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity $O({\epsilon }^{-2}{d}^{1/2+o(1)})$, independent of $n$. Up to the $d^{o(1)}$-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $n$ yields a non-adaptive, one-sided $O({\epsilon }^{-2}{d}^{1/2+o(1)})$-query monotonicity tester for Boolean functions $f:{\mathbb{R}}^d\to \{0,1\}$ associated with an arbitrary product measure.

Accepted to SICOMP. This version has been revised fairly significantly since the preliminary version which appeared at FOCS 2023