Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries

Mark Chen, Xi Chen, Hao Cui +2

We show that for any constant $c>0$, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity $\Omega (n^{1/2-c})$. This improves…