Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions in $d$-Dimensions

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We describe a $\tilde{O}(d^{5/6})$-query monotonicity tester for Boolean functions $f:[n{]}^d\to \{0,1\}$ on the $n$-hypergrid. This is the first $o(d)$ monotonicity tester with que…