## A Polynomial Lower Bound for Testing Monotonicity

by Aleksandrs Belovs and Eric Blais

The main result is an $\tilde\Omega(\ell^{1/4})$ lower bound on query complexity of general testers for monotonicity of $\ell$-variate Boolean functions. Prior results established that the query complexity of non-adaptive testers for this property is $\tilde\Theta({\sqrt\ell})$.