Description
A Probably Approximately Correct Lower Bound for Boolean Monotonicity Testing
Boolean function monotonicity testing is a problem that has received a lot of attention in the property testing community. In recent joint work with Xi Chen and Rocco Servedio (FOCS 2014), we gave an $\tilde{\Omega}(n^{1/5})$ lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown $n$-variable Boolean function is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of $\Omega(\log n)$ for this model due to Fischer et al. from 2002.
More recently, in joint work with Xi Chen, Anindya De, and Rocco Servedio, we extended this lower bound to $\Omega(n^{1/2}-c)$ for any $c > 0$. If one believes (as is commonly conjectured) that the true non-adaptive query complexity of monotonicity testing is
$\Theta(\sqrt{n})$, this new lower bound is probably approximately correct.
In this talk I will present the main ideas behind these recent results and talk about directions for future work on the monotonicity testing
problem.