A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Monotonicity testing of Boolean functions on the hypergrid, $f:[n{]}^d\to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem i…