Upper and lower bounds for some depth-3 circuit classes |
| |
| Authors: | Richard Beigel Alexis Maciel |
| |
| Affiliation: | (1) Department of Computer Science and UMIACS, University of Maryland, 20742 College Park, MD, USA;(2) Present address: Department of EE&CS Packard Lab, Lehigh University, 19 Memorial Drive West, 18015 Bethlehem, PA, USA;(3) Department of Computer Science and UMIACS, University of Maryland, 20742 College Park, MD, USA;(4) Present address: Department of Mathematics and Computer Science, Clarkson University, 13699-5815 Potsdam, NY, USA |
| |
| Abstract: | We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MOD
m
gates at level one. We show that the fan-in of the AND gates can be reduced toO(logn) in the case wherem is unbounded, and to a constant in the case wherem is constant. We then use these upper bounds to derive exponential lower bounds for this class of circuits. In the unboundedm case, this yields a new proof of a lower bound of Grolmusz; in the constantm case, our result sharpens his lower bound. In addition, we prove an exponential lower bound if OR gates are also permitted on level two andm is a constant prime power.Dedicated to the memory of Roman Smolensky |
| |
| Keywords: | Threshold circuit constant depth majority gate MOD gate inner product mod 2 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
