caa a22 4500 469033975 CHVBK 20180323132751.0 cr unu---uuuuu 170328e19921201xx s 000 0 eng 10.1007/BF01200426 doi (NATIONALLICENCE)springer-10.1007/BF01200426 Majority gates vs. general weighted threshold gates [Elektronische Daten] [Mikael Goldmann, Johan Håstad, Alexander Razborov] In this paper we study small depth circuits that contain threshold gates (with or without weights) and parity gates. All circuits we consider are of polynomial size. We prove several results which complete the work on characterizing possible inclusions between many classes defined by small depth circuits. These results are the following: 1. A single threshold gate with weights cannot in general be replaced by a polynomial fan-in unweighted threshold gate of parity gates. 2. On the other hand it can be replaced by a depth 2 unweighted threshold circuit of polynomial size. An extension of this construction is used to prove that whatever can be computed by a depthd polynomial size threshold circuit with weights can be computed by a depthd+1 polynomial size unweighted threshold circuit, whered is an arbitrary fixed integer. 3. A polynomial fan-in threshold gate (with weights) of parity gates cannot in general be replaced by a depth 2 unweighted threshold circuit of polynomial size. Birkhäuser Verlag, 1992 circuit complexity nationallicence majority circuits nationallicence threshold circuits nationallicence lower bounds nationallicence 68Q15 nationallicence Goldmann Mikael Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44, Stockholm, SWEDEN aut Håstad Johan Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44, Stockholm, SWEDEN aut Razborov Alexander Steklov Mathematical Institute, Vavilova, 42, 117966, GSP-1, Moscow, RUSSIA aut computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 277-300 1016-3328 2:4<277 1992 2 37 https://doi.org/10.1007/BF01200426 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01200426 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Goldmann Mikael Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44, Stockholm, SWEDEN aut NATIONALLICENCE 700 1- Håstad Johan Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44, Stockholm, SWEDEN aut NATIONALLICENCE 700 1- Razborov Alexander Steklov Mathematical Institute, Vavilova, 42, 117966, GSP-1, Moscow, RUSSIA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag 2/4(1992-12-01), 277-300 1016-3328 2:4<277 1992 2 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer