UPPER AND LOWER BOUNDS FOR SOME DEPTH-3 CIRCUIT CLASSES

We investigate the complexity of depth-3 threshold circuits with major ity gates at the output, possibly negated AND gates at level two, and MODm gates at level one. We show that the fan-in of the AND gates can be reduced to O(log n) in the case where m is unbounded, and to a cons tant in the case where m is constant. We then use these upper bounds t o derive exponential lower bounds for this class of circuits. In the u nbounded m case, this yields a new proof of a lower bound of Grolmusz; in the constant m case, our result sharpens his lower bound. In addit ion, we prove an exponential lower bound if OR gates are also permitte d on level two and m is a constant prime power.