# A polynomial lower bound for monotonicity testing of Boolean functions over hypercube and hypergrid domains

We prove a $$\tilde{\Omega}(n^{1/5})$$ lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown n-variable Boolean function is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of $$\Omega(\log n)$$ due to Fischer et al from 2002. Our approach extends to give a similar lower bound for monotonicity testing of Boolean-valued functions over certain hypergrid domains $$\{1,2,...,m\}^n$$. Joint work with Li-Yang Tan.

### Affiliation

Columbia University

Rocco Servedio