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 Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{ O}(\varepsilon^{ -2}\sqrt{ d})$ queries. Up to polylog $d$ and $\varepsilon$ factors, this bound matches the $\widetilde{ \Omega}(\sqrt{ d})$-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any $n > 2$, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a $\widetilde{ O}(d^{ 5/6})$-query upper bound (SODA 2020), quite far from the $\sqrt{ d}$ bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant $n$, up to $\text{ poly}(\varepsilon^{ -1}\log d)$ factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making $\widetilde{ O}(\varepsilon^{ -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.
Categories: cs.DS cs.DM