2022/11/10 by Black, Hadley, Chakrabarty, Deeparnab, Seshadhri, C.
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2211.05281
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 \widetildeO(ε-2√(d)) queries. Up to polylog d and ε factors, this bound matches the \widetildeΩ(√(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 \widetildeO(d5/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(ε-1log d) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making \widetildeO(ε-2n√(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.