{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T19:43:38Z","timestamp":1782589418280,"version":"3.54.5"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01272517","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T07:41:27Z","timestamp":1111650087000},"page":"113-129","source":"Crossref","is-referenced-by-count":140,"title":["On the power of small-depth threshold circuits"],"prefix":"10.1007","volume":"1","author":[{"given":"Johan","family":"H\ufffdstad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikael","family":"Goldmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai. ? 1 1 on finite structures.Annals of Pure and Applied Logic, 24:1?48, 1983.","journal-title":"Annals of Pure and Applied Logic"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"E. Allender. A note on the power of threshold circuits.Proceedings 30'th Annual Symposium on Foundations of Computer Science, pages 580?584, 1989.","DOI":"10.1109\/SFCS.1989.63538"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R. B. Boppana. The monotone circuit complexity of boolean functions.Combinatorica, 7:1?22, 1987.","journal-title":"Combinatorica"},{"key":"CR4","first-page":"1033","volume":"282","author":"A. E. Andreev","year":"1985","unstructured":"A. E. Andreev. On a method for obtaining lower bounds for the complexity of individual monotone functions.Dokl. Ak. Nauk. SSSR 282, pages 1033?1037, 1985. English translation inSov. Math. Dokl., 31:530?534, 1985.","journal-title":"Dokl. Ak. Nauk. SSSR"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, N. Nisan, and M. Szegedy. Multipary protocols and logspacehard pseudorandom sequences.Proceedings of 21 st Annual ACM Symposium on Theory of Computing, pages 1?11, 1989.","DOI":"10.1145\/73007.73008"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"P. W. Beame, S. A. Cook, and H. J. Hoover. Log depth circuits for division and related problems.Proceedings 25'th Annual Symposium on Foundations of Computer Science, pages 1?6, 1984.","DOI":"10.1109\/SFCS.1984.715894"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility.SIAM J. on Computing, 13:423?439, 1984.","journal-title":"SIAM J. on Computing"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"B. Chor","year":"1988","unstructured":"B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity.SIAM J. on Computing, 17:230?261, 1988.","journal-title":"SIAM J. on Computing"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial time hierarchy.Math. System Theory, 17:13?27, 1984.","journal-title":"Math. System Theory"},{"key":"CR10","unstructured":"J. Hastad.Computational Limitations of Small-Depth Circuits. MIT PRESS, 1986."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"J. Hastad and M. Goldmann. On the power of small-depth threshold circuits.Proceedings 31st Annual IEEE Symposium on Foundations of Computer Science, pages 610?618, 1990.","DOI":"10.1109\/FSCS.1990.89582"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, and G. Tur\u00e1n. Threshold circuits of bounded depth.Proceedings 28th Annual IEEE Symposium on Foundation of computer science, pages 99?110, 1987.","DOI":"10.1109\/SFCS.1987.59"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. InProceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988.","DOI":"10.1145\/62212.62265"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson. Probabilistic communication complexity of boolean relations. InProceedings of the 30th Annual IEEE Symposium on Foundation of computer science, pages 562?567, 1989.","DOI":"10.1109\/SFCS.1989.63535"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson. Monotone circuits for matching require linear depth.22nd annual ACM Symposium on Theory of Computing, pages 287?292, 1990.","DOI":"10.1145\/100216.100253"},{"issue":"6","key":"CR16","first-page":"887","volume":"37","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov. Lower bounds on monotone network complexity of the logical permanent.Matem. Zam., 37(6):887?900, 1985. English translation inMath. Notes of the Academy of Sciences of the USSR, 37:485?493, 1985.","journal-title":"Matem. Zam."},{"issue":"4","key":"CR17","first-page":"598","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"A. 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?607, 1987. English translation in 41:4, pages 333?338.","journal-title":"Mathematical Notes of the Academy of Sciences of the USSR"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"M. Sipser. Borel sets and circuit complexity. InProceedings of 15th Annual ACM Symposium on Theory of Computing, pages 61?69, 1983.","DOI":"10.1145\/800061.808733"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity.Proceedings of 19th Annual ACM Symposium on Theory of Computing, pages 77?82, 1987.","DOI":"10.1145\/28395.28404"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"S. Toda. On the computational power ofPP and ?P. Proceedings 30th Annual IEEE Symposium on Foundations of Computer Science, pages 514?519, 1989.","DOI":"10.1109\/SFCS.1989.63527"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"A. Yao. Separating the polynomial-time hierarchy by oracles.Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science, pages 1?10, 1985.","DOI":"10.1109\/SFCS.1985.49"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"A. Yao. Circuits and local computation.Proceedings of 21 st Annual ACM Symposium on Theory of Computing, pages 186?196, 1989.","DOI":"10.1145\/73007.73025"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"A. Yao. OnACC and threshold circuits.Proceedings 31 st Annual IEEE Symposium on Foundations of Computer Science, pages 619?627, 1990.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01272517.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01272517\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01272517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T10:30:21Z","timestamp":1735381821000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01272517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01272517"],"URL":"https:\/\/doi.org\/10.1007\/bf01272517","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}