Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-002 | 28th January 1997 00:00

Upper and Lower Bounds for Some Depth-3 Circuit Classes

RSS-Feed




TR97-002
Authors: Richard Beigel, Alexis Maciel
Publication: 29th January 1997 09:28
Downloads: 932
Keywords: 


Abstract:

We investigate the complexity of depth-3 threshold circuits
with majority 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 constant in the
case where m is constant. We then use these upper bounds to
derive exponential lower bounds for this class of circuits.
In the unbounded 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 addition, we prove an
exponential lower bound if OR gates are also permitted on
level two and m is a constant prime power.



ISSN 1433-8092 | Imprint