A note on the power of threshold circuits
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 580-584
- https://doi.org/10.1109/sfcs.1989.63538
Abstract
The author presents a very simple proof of the fact that any language accepted by polynomial-size depth-k unbounded-fan-in circuits of AND and OR gates is accepted by depth-three threshold circuits of size n raised to the power O(log/sup k/n). The proof uses much of the intuition of S. Toda's result that the polynomial hierarchy is contained in P/sup Hash P/ (30th Ann. Symp. Foundations Comput. Sci., p.514-519, 1989).Keywords
This publication has 16 references indexed in Scilit:
- The complexity of iterated multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On Threshold Circuits and Polynomial ComputationSIAM Journal on Computing, 1992
- Parallel computation with threshold functionsJournal of Computer and System Sciences, 1988
- Hardness vs. randomnessPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Decision trees and downward closuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Random oracles separate PSPACE from the polynomial-time hierarchyInformation Processing Letters, 1987
- Algebraic methods in the theory of lower bounds for Boolean circuit complexityPublished by Association for Computing Machinery (ACM) ,1987
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- A complexity theoretic approach to randomnessPublished by Association for Computing Machinery (ACM) ,1983
- Borel sets and circuit complexityPublished by Association for Computing Machinery (ACM) ,1983