Title :
On the power of small-depth threshold circuits
Author :
Håstad, Johan ; Goldmann, Mikael
Author_Institution :
R. Inst. of Technol., Stockholm, Sweden
Abstract :
The power of threshold circuits of small depth is investigated. In particular, functions that require exponential-size unweighted threshold circuits of depth 3 when the bottom fan-in is restricted are given. It is proved that there are monotone functions fk that can be computed on depth k and linear size AND, OR circuits but require exponential-size to be computed by a depth-(k-1) monotone weighted threshold circuit
Keywords :
combinatorial switching; threshold logic; AND; OR circuits; bottom fan-in; functions; monotone functions; monotone weighted threshold circuit; small-depth threshold circuits; Circuits; Complexity theory; Cost function; Polynomials; Probability distribution; Protocols;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89582