Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of $n$: There are testers ... more >>>

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})\cdot \text{poly}(\log n,1/\epsilon)$. Previous to our work, the best known testers had query complexity linear in $d$ but independent of $n$. We improve upon these testers as ... more >>>