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

arXiv: https://arxiv.org/abs/2211.05281 · HTML: https://mlsanity.com/paper/2211.05281/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2022.

## Built on by (most cited first, 1 of 1)

- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)

## Abstract (arXiv)

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(varepsilon-2√d) queries. Up to polylog d and varepsilon factors, this bound matches the widetildeOmega(√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(varepsilon-1log d) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making widetildeO(varepsilon-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.