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 \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.