An optimal lower bound for monotonicity testing over hypergrids

Deeparnab Chakrabarty, C. Seshadhri

For positive integers $n,d$, consider the hypergrid $[n{]}^d$ with the coordinate-wise product partial ordering denoted by $\prec$. A function $f:[n{]}^d\mapsto \mathbb{N}$ is monot…