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

X. Chen and
A. De and
R. Servedio and
L.-Y. Tan.

In *47th Annual Symposium on Foundations
of Computer Science (STOC),* 2015, pp. 519--528.

**Abstract:**
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 is monotone versus constant-far from monotone. This improves an $\Omega(n^{1/5})$ lower bound for the same problem that was recently given in [CST14] and is very close to $\Omega(n^{1/2})$,
which we conjecture is the optimal lower bound for this model.

Link to full version on ArXiV

Back to
main papers page