  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.
