ECCC-Report TR22-162https://eccc.weizmann.ac.il/report/2022/162Comments and Revisions published for TR22-162en-usSun, 20 Nov 2022 07:41:10 +0200
Paper TR22-162
| Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester |
Hadley Black,
Deeparnab Chakrabarty,
C. Seshadhri
https://eccc.weizmann.ac.il/report/2022/162The 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.Sun, 20 Nov 2022 07:41:10 +0200https://eccc.weizmann.ac.il/report/2022/162