SEPARATING AC0 FROM DEPTH-2 MAJORITY CIRCUITS.

We construct a function in AC⁰ that cannot be computed by a depth-2 majority circuit of size less than exp(ϴ(n^1/5)). This solves an open problem due to Krause and Pudlák [Theoret. Comput. Sci., 174 (1997), pp. 137-156] and matches Allender's classic result [A note on the power of threshold circuits, in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Research Triangle Park, NC, 1989, pp. 580-584] that AC⁰ can be efficiently simulated by depth-3 majority circuits. To obtain our result, we develop a novel technique for proving lower bounds on communication complexity. This technique, the Degree/Discrepancy Theorem, is of independent interest. It translates lower bounds on the threshold degree of any Boolean function into upper bounds on the discrepancy of a related function. Upper bounds on the discrepancy, in turn, immediately imply lower bounds on communication and circuit size. In particular, we exhibit the first known function in AC⁰ with exponentially small discrepancy, exp(-Ω(n^1/5)), thereby establishing the separations Σ^cc₂... PP^cc and Π^cc₂ ... PP^cc in communication complexity. [ABSTRACT FROM AUTHOR]