  We prove a lower bound of $\tilde{\Omega}(n^{1/3})$ for the query complexity
of any two-sided and adaptive algorithm that tests whether an unknown Boolean
function $f:\{0,1\}^n\rightarrow \{0,1\}$ is monotone or far from monotone.
This improves the recent bound of $\tilde{\Omega}(n^{1/4})$ for the same
problem by Belovs and Blais [BB15]. Our result builds on a new family of random
Boolean functions that can be viewed as a two-level extension of Talagrand's
random DNFs.
  Beyond monotonicity, we also prove a lower bound of $\tilde{\Omega}(n^{2/3})$
for any two-sided and adaptive algorithm, and a lower bound of
$\tilde{\Omega}(n)$ for any one-sided and non-adaptive algorithm for testing
unateness, a natural generalization of monotonicity. The latter matches the
recent linear upper bounds by Khot and Shinkar [KS15] and by Chakrabarty and
Seshadhri [CS16].

Computational Complexity