A $o(d)\cdot \text{polylog}n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n{]}^d$

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n{]}^d$ and design a non-adaptive tester with $1$-sided error whose query complexity is $\tilde{O}(d^{5/6})\cd…