We investigate the complexity of depth-3 threshold circuitswith majority gates at the output, possibly negated ANDgates at level two, and MODm gates at level one. We showthat the fan-in of the AND gates can be reduced to O(log n)in the case where m is unbounded, and to a constant in thecase where m is constant. We then use these upper bounds toderive exponential lower bounds for this class of circuits.In the unbounded m case, this yields a new proof of a lowerbound of Grolmusz; in the constant m case, our resultsharpens his lower bound. In addition, we prove anexponential lower bound if OR gates are also permitted onlevel two and m is a constant prime power.
展开▼
