2010 · 27 citations · 29 references
ComputingComputer ScienceAlgorithmsCircuit TheoryTheory Of ComputationBoolean AlgebraBoolean OperationsCircuit ComplexityDigital Logic DesignLogic SynthesisBoolean Circuit ComplexityBoolean Circuit DesignCircuit Complexity HierarchiesCircuit Lower BoundsConstant-depth CircuitsLower BoundsThreshold CircuitsThreshold Logic
We initiate a systematic study of constant depth Boolean circuits built using exact threshold gates. We consider both unweighted and weighted exact threshold gates and introduce corresponding circuit classes. We next show that this gives a hierarchy of classes that seamlessly interleave with the well-studied corresponding hierarchies defined using ordinary threshold gates. A major open problem in Boolean circuit complexity is to provide an explicit super-polynomial lower bound for depth two threshold circuits. We identify the class of depth two exact threshold circuits as a natural subclass of these where also no explicit lower bounds are known. Many of our results can be seen as evidence that this class is a strict subclass of depth two threshold circuits --- thus we argue that efforts in proving lower bounds should be directed towards this class.
29
Introduction to the theory of neural computation
Neural Networks · 1994 · 6.5K citations
Introduction to the Theory of Neural Computation
John Hertz, Anders Krogh, Richard Palmer et al. · American Journal of Physics · 1994 · 1.3K citations · Full text
Complexity classes in communication complexity theory
László Babai, Péter Frankl, Janoš Šimon · 1986 · 318 citations · Full text
Ashok K. Chandra, Larry Stockmeyer, Uzi Vishkin · SIAM Journal on Computing · 1984 · 297 citations