  This paper gives the first separation between the power of {\em formulas} and
{\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded
fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log
n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits}
that are not equivalent to {\em depth-$d$ formulas of size $n^{o(d)}$}
(moreover, this is optimal in that $n^{o(d)}$ cannot be improved to
$n^{O(d)}$). This result is obtained by a combination of new lower and upper
bounds for {\em Approximate Majorities}, the class of Boolean functions
$\{0,1\}^n \to \{0,1\}$ that agree with the Majority function on $3/4$ fraction
of inputs.
  $\mathrm{AC}^0[\oplus]$ formula lower bound: We show that every depth-$d$
$\mathrm{AC}^0[\oplus]$ formula of size $s$ has a {\em $1/8$-error polynomial
approximation} over $\mathbb{F}_2$ of degree $O(\frac{1}{d}\log s)^{d-1}$. This
strengthens a classic $O(\log s)^{d-1}$ degree approximation for
\underline{circuits} due to Razborov. Since the Majority function has
approximate degree $\Theta(\sqrt n)$, this result implies an
$\exp(\Omega(dn^{1/2(d-1)}))$ lower bound on the depth-$d$
$\mathrm{AC}^0[\oplus]$ formula size of all Approximate Majority functions for
all $d(n) \le O(\log n)$.
  Monotone $\mathrm{AC}^0$ circuit upper bound: For all $d(n) \le O(\frac{\log
n}{\log\log n})$, we give a randomized construction of depth-$d$ monotone
$\mathrm{AC}^0$ circuits (without NOT or MOD$_2$ gates) of size
$\exp(O(n^{1/2(d-1)}))$ that compute an Approximate Majority function. This
strengthens a construction of \underline{formulas} of size
$\exp(O(dn^{1/2(d-1)}))$ due to Amano.
