Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the nonadaptive complexity of this problem is an important open question. For arbitrary $n$, [BlackChakrabartySeshadhri, 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, [BravermanKhotKindlerMinzer, ITCS 2023] and [BlackChakrabartySeshadhri, 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$. \smallskip In this paper, we describe a nonadaptive, onesided monotonicity tester with query complexity $O(\varepsilon^{2} d^{1/2 + o(1)})$, \emph{independent} of $n$. Up to the $d^{o(1)}$factors, our result resolves the nonadaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $n$ yields a nonadaptive, onesided $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.more » « lessFree, publiclyaccessible full text available November 6, 2024

The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of KhotMinzerSafra (FOCS 2015) gave a nonadaptive, onesided tester making $\otilde(\eps^{2}\sqrt{d})$ queries. Up to polylog $d$ and $\eps$ factors, this bound matches the $\widetilde{\Omega}(\sqrt{d})$query nonadaptive lower bound (ChenDeServedioTan (STOC 2015), ChenWaingartenXie (STOC 2017)). For any $n > 2$, the optimal nonadaptive complexity was unknown. A previous result of the authors achieves a $\otilde(d^{5/6})$query upper bound (SODA 2020), quite far from the $\sqrt{d}$ bound for the hypercube. In this paper, we resolve the nonadaptive complexity of monotonicity testing for all constant $n$, up to $\poly(\eps^{1}\log d)$ factors. Specifically, we give a nonadaptive, onesided monotonicity tester making $\otilde(\eps^{2}n\sqrt{d})$ queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid $[n]^d$. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.more » « less