  The approximate degree of a Boolean function $f \colon \{-1, 1\}^n
\rightarrow \{-1, 1\}$ is the least degree of a real polynomial that
approximates $f$ pointwise to error at most $1/3$. We introduce a generic
method for increasing the approximate degree of a given function, while
preserving its computability by constant-depth circuits.
  Specifically, we show how to transform any Boolean function $f$ with
approximate degree $d$ into a function $F$ on $O(n \cdot
\operatorname{polylog}(n))$ variables with approximate degree at least $D =
\Omega(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-\Omega(1)}$, then
$D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a
polynomial-size Boolean circuit of constant depth, then so is $F$.
  By recursively applying our transformation, for any constant $\delta > 0$ we
exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This
improves over the best previous lower bound of $\Omega(n^{2/3})$ due to
Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of
$n$ that holds for any function. Our lower bounds also apply to
(quasipolynomial-size) DNFs of polylogarithmic width.
  We describe several applications of these results. We give:
  * For any constant $\delta > 0$, an $\Omega(n^{1-\delta})$ lower bound on the
quantum communication complexity of a function in AC$^0$.
  * A Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$,
where $C(f)$ is the certificate complexity of $f$. This separation is optimal
up to the $o(1)$ term in the exponent.
  * Improved secret sharing schemes with reconstruction procedures in AC$^0$.
