{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:21:25Z","timestamp":1775053285568,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540557067","type":"print"},{"value":"9783540472759","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55706-7_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:33:52Z","timestamp":1330252432000},"page":"42-52","source":"Crossref","is-referenced-by-count":14,"title":["On small depth threshold circuits"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Razborov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"4_CR1","unstructured":"N. Alon and J. Bruck. Explicit constructions of depth-2 majority circuits for comparison and addition. Technical Report RJ 8300 (75661), IBM Research Division, August 1991."},{"key":"4_CR2","unstructured":"D. A. Barrington. A note on a theorem of Razborov. Technical report, University of Massachusetts, 1986."},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. Beame","year":"1986","unstructured":"P. Beame, S. Cook, and H. Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15:994\u20131003, 1986.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"4_CR4","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1109\/12.45216","volume":"39","author":"Y. Brandman","year":"1990","unstructured":"Y. Brandman, A. Orlitsky, and J. Hennesy. A spectral lower bound technique for the size of decision trees and two-level AND\/OR circuits. IEEE Transactions on Computers, 39(2):282\u2013287, February 1990.","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"4_CR5","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"J. Bruck. Harmonic analysis of polynomial threshold functions. SIAM Journal on Discrete Mathematics, 3(2):168\u2013177, May 1990.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"4_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J. Bruck","year":"1992","unstructured":"J. Bruck and R. Smolensky. Polynomial threshold functions, AC 0 functions and spectral norms. SIAM Journal on Computing, 21(1):33\u201342, February 1992.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. K. Chandra","year":"1984","unstructured":"A. K. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13:423\u2013439, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"M. Goldmann, J. H\u00e5stad, and A. Razborov. Majority gates vs. general weighted threshold gates. In Proceedings of the 7 th Structure in Complexity Theory Annual Conference, 1992.","DOI":"10.1109\/SCT.1992.215375"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad and M. Goldmann. On the power of small-depth threshold circuits. In Proceedings of the 31st IEEE FOCS, pages 610\u2013618, 1990.","DOI":"10.1109\/FSCS.1990.89582"},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(91)90183-I","volume":"39","author":"T. Hofmeister","year":"1991","unstructured":"T. Hofmeister, W. Honberg, and S. K\u00f6ling. Some notes on threshold circuits and multiplication in depth 4. Information Processing Letters, 39:219\u2013225, 1991.","journal-title":"Information Processing Letters"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"J. Hertz, R. Krogh, and A. Palmer. An Introduction to the Theory of Neural Computation. Addison-Wesley, 1991.","DOI":"10.1063\/1.2810360"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, and G. Tur\u00e1n. Threshold circuits of bounded depth. In Proceedings of 28th IEEE FOCS, pages 99\u2013110, 1987.","DOI":"10.1109\/SFCS.1987.59"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai, and Linial N. The influence of variables on Boolean functions. In Proceedings of the 29 th IEEE Symposium on Foundations of Computer Science, pages 68\u201380, 1988.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. In Proceedings of the 23rd ACM STOC, pages 455\u2013464, 1991.","DOI":"10.1145\/103418.103466"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"M. Krause. Geometric arguments yield better bounds for threshold circuits and distributed computing. In 6-th Structure in Complexity Theory Conference, pages 314\u2013322, 1991.","DOI":"10.1109\/SCT.1991.160275"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"M. Krause and S. Waack. Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in. In Proceedings of the 32th IEEE Symposium on Foundations of Computer Science, pages 777\u2013782, 1991.","DOI":"10.1109\/SFCS.1991.185448"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transforms and learnability. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 574\u2013579, 1989.","DOI":"10.1109\/SFCS.1989.63537"},{"issue":"2","key":"4_CR18","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1109\/TEC.1961.5219204","volume":"EC10","author":"J. Myhill","year":"1961","unstructured":"J. Myhill and W.H. Kautz. On the size of weights required for linear-input switching functions. IRE Trans. on Electronic Computers, EC10(2):288\u2013290, June 1961.","journal-title":"IRE Trans. on Electronic Computers"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"W. Maass, G. Schnitger, and E. Sontag. On the computational power of sigmoid versus boolean threshold circuits. In Proceedings of the 32nd IEEE Symposium on Foundations of Computer Science, pages 767\u2013776, 1991.","DOI":"10.1109\/SFCS.1991.185447"},{"key":"4_CR20","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1147\/rd.312.0235","volume":"31","author":"N. Pippenger","year":"1987","unstructured":"N. Pippenger. The complexity of computations by networks. IBM J. Res. Develop., 31:235\u2013243, 1987.","journal-title":"IBM J. Res. Develop."},{"issue":"4","key":"4_CR21","first-page":"598","volume":"41","author":"A. Razborov","year":"1987","unstructured":"A. Razborov. Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):598\u2013607, 1987. English translation in 41:4, pages 333\u2013338.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"issue":"3","key":"4_CR22","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0404038","volume":"4","author":"K.-I. Siu","year":"1991","unstructured":"K.-I. Siu and J. Bruck. On the power of threshold circuits with small weights. SIAM Journal on Discrete Mathematics, 4(3):423\u2013435, 1991.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4_CR23","unstructured":"K.-I. Siu, J. Bruck, T. Kailath, and T. Hofmeister. Depth-efficient neural networks for division and related problems. Technical Report RJ 7946, IBM Research, January 1991. To appear in IEEE Trans. Information Theory."},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 77\u201382, 1987.","DOI":"10.1145\/28395.28404"},{"key":"4_CR25","unstructured":"K.-Y. Siu and V. Roychowdhury. On optimal depth threshold circuits for multiplication and related problems. Manuscript, 1992."},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"A. Yao. Some complexity questions related to distributive computing. In Proceedings of the 11th ACM STOC, pages 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"A. Yao. On ACC and threshold circuits. In Proceedings of the 31th IEEE FOCS, pages 619\u2013627, 1990.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '92"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55706-7_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:01:29Z","timestamp":1605646889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55706-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557067","9783540472759"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-55706-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}