Being preoccupied with other things, I put aside looking at recent ECCC announcements. I still cannot afford studying this work at depth, but felt that I should put a recommendation for the result.
As is not stated in the paper, this work focuses on a testing problem that was put forward and initially studied in the first paper on monotonicity testing. In full generality, the aim is to test monotonicity of function from $[n]^d$ to $[m]$, whereas the current work considers the case of $m=2$. Of course, subsequent works have greatly improved over the aforementioned initial study, where key improvements are the elimination of the dependence on $n$ (here) and the celebrated KMS18 that provided an almost optimal result for the case of $n=m=2$.
The current work aims at achieving the best of both worlds, and succeeds in doing so. Specifically, for $m=2$ and arbitrary $n$, it describes a non-adaptive, one-sided tester of query complexity $O(\epsilon^{-2} d^{1/2 + o(1)})$, where $\epsilon $ denotes the proximity parameter.
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 $\widetilde{O}(\varepsilon^{-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 $\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$ and $\widetilde{O}(\varepsilon^{-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(\varepsilon^{-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(\varepsilon^{-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.
See ECCC TR23-048.