Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester

The problem of testing monotonicity for Boolean functions on the hypergrid, f :[ n ] d → {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 O (ε −2 √ d ) queries. Up to polylog d and ε factors, this bound matches the Ω(√ 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 O ( d 5/6 )-query upper bound (SODA 2020), quite far from the √ d bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant n , up to poly (ε −1 log d ) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making O (ε −2 n √ 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.

Authors

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

Keywords

• Boolean Functions
• Isoperimetry Theorems
• Monotonicity Testing
• Property Testing