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

Xi Chen, Anindya De, Rocco A. Servedio +1

We prove a lower bound of $\Omega (n^{1/2-c})$, for all $c>0$, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$-variable Boolean function…