Title :
Majority gates vs. general weighted threshold gates
Author :
Goldmann, Mikael ; Håstad, Johan ; Razborov, Alexander
Author_Institution :
R. Inst. of Technol., Stockholm, Sweden
Abstract :
Small-depth circuits that contain threshold gates (with or without weights) and parity gates are studied. All circuits considered are of polynomial size. Several results that complete the work of characterizing possible inclusions between many classes defined by small-depth circuits are proved
Keywords :
computational complexity; logic gates; majority logic; threshold elements; threshold logic; majority gates; parity gates; polynomial size gates; small-depth circuits; weighted threshold gates; Circuits; Computational modeling; Computer science; Neural networks; Neurofeedback; Physics computing; Polynomials; Wires;
Conference_Titel :
Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
Conference_Location :
Boston, MA
Print_ISBN :
0-8186-2955-X
DOI :
10.1109/SCT.1992.215375
