This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the AC 0 [ ] basis (unbounded fan-in AND, OR, NOT and MOD 2 gates). We show, for all d ( n ) O ( 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 0 1 that agree with the Majority function on 3 4 fraction of inputs.

AC 0 [ ] formula lower bound: We show that every depth- d AC 0 [ ] formula of size s has a {\em 1 8 -error polynomial approximation} over \F 2 of degree O ( 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 ( n ) , this result implies an exp ( ( d n 1 2( d − 1) )) lower bound on the depth- d AC 0 [ ] formula size of all Approximate Majority functions for all d ( n ) O ( log n ) .

Monotone AC 0 circuit upper bound: For all d ( n ) O ( log n log log n ) , we give a randomized construction of depth- d monotone 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 ( d n 1 2( d − 1) )) due to Amano.