Multiparty communication complexity and threshold circuit size of AC\(^0\) (Q2910850)

The class \(\mathrm{AC}^0\) of all functions computable by Boolean circuit families of polynomial size and constant depth over unbounded gates cannot compute functions such as parity and majority. On the other hand, Allender showed that each function in AC\(^0\) can be computed by circuit families of quasipolynomial size and depth 3 over majority gates. This was improved by Yao who obtained a simulation by quasipolynomial-size \(\mathrm{MAJ} \circ \mathrm{SYM} \circ \mathrm{AND}\) circuits; these are circuits consisting of a majority gate on top, a symmetric gate at the next level, and AND gates of polylogarithmic fan-in at the bottom level. (Further improvements have been given by Beigel, Tarui, and others.) A long standing question is if these simulations can actually be improved to polynomial size.NEWLINENEWLINEThe complexity issues for \(\mathrm{MAJ} \circ \mathrm{SYM} \circ \mathrm{AND}\) circuits related to multiparty communication complexity are known where every input value can be seen by all but one of the players; this is the so called number-on-forehead (NOF) model. The main result of the present paper is a superpolynomial lower bound for the communication complexity of a fixed \(\mathrm{AC}^0\) function (a function which is, in fact, computable by depth-6 \(\mathrm{AC}^0\) circuits) in this model. A consequence is that quasipolynomial size is necessary in Yao's simulation of \(\mathrm{AC}^0\).