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

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 Theory of Computing (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