A Polynomial Lower Bound for Testing Monotonicity

Abstract

We show that every algorithm for testing $n$-variate Boolean functions for monotonicity must have query complexity $\tilde{\Omega }(n^{1/4})$. All previous lower bounds for this problem were designed for non-adaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only $\Omega (\log n)$. Combined with the query complexity of the non-adaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity. By contrast, we show that there is an exponential gap between the query complexity of adaptive and non-adaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that non-adaptive algorithms require almost $\Omega (n^{1/2})$ queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity $O(\log n)$ when the input is a regular LTF.

22 pages