A polynomial lower bound for testing monotonicity

We show that every algorithm for testing n-variate Boolean functions for monotonicity must have query complexity Ω (n1/4). All previous lower bounds for this problem were designed for nonadaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only Ω (log n). Combined with the query complexity of the nonadaptive 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 nonadaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that nonadaptive algorithms require almost Ω (n1/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.