{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T00:52:33Z","timestamp":1778028753492,"version":"3.51.4"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"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":[[1995,6]]},"DOI":"10.1007\/bf01268140","type":"journal-article","created":{"date-parts":[[2005,3,23]],"date-time":"2005-03-23T22:03:06Z","timestamp":1111615386000},"page":"99-112","source":"Crossref","is-referenced-by-count":22,"title":["Top-down lower bounds for depth-three circuits"],"prefix":"10.1007","volume":"5","author":[{"given":"J.","family":"H\ufffdstad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Jukna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Pudl\ufffdk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"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, 111-1 on finite structures.Ann. Pure and Appl. Logic 24 (1983), 1?48.","journal-title":"Ann. Pure and Appl. Logic"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov andR. Smolensky, On lower bounds for reak-k-times branching programs.Computational Complexity 3 (1993), 1?18.","journal-title":"Computational Complexity"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\ufffds","year":"1960","unstructured":"P. Erd\ufffds andR. Rado, Intersection theorems for systems of sets.J. London Math. Soc. 35 (1960), 85?90.","journal-title":"J. London Math. Soc."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe andM. Sipser, Parity, circuits and the polynomial time hierarchy.Math. Systems Theory 17 (1984), 13?27.","journal-title":"Math. Systems Theory"},{"key":"CR5","unstructured":"J. H\ufffdstad,Almost Optimal Lower Bounds for Small Depth Circuits. Advances in Computing Research, ed.S. Micali, Vol 5 (1989), 143?170."},{"key":"CR6","unstructured":"S. Jukna,Finite limits and lower bounds for circuit size. Tech. Rep. 94-06, Informatik, University of Trier, 1994."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"M. Karchmer andA. Wigderson, Monotone circuits for connectivity require super-logarithmic depth.SIAM J. Disc. Math. 3 (1990), 255?265.","journal-title":"SIAM J. Disc. Math."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"M. Klawe, W. J. Paul, N. Pippenger, M. Yannakakis, On monotone formulae with restricted depth. InProc. Sixteenth Ann. ACM Symp. Theor. Comput., 1984, 480?487.","DOI":"10.1145\/800057.808717"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Monotone circuits for matching require linear depth. InProc. Twenty-second Ann. ACM Symp. Theor. Comput., 1990, 287?292.","DOI":"10.1145\/100216.100253"},{"issue":"4","key":"CR10","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"A. A. Razborov, Lower bounds for the size of circuits of bounded depth with basis {?, ?}.Math. Notes of the Academy of Sciences of the USSR 41:4 (1987), 333?338.","journal-title":"Math. Notes of the Academy of Sciences of the USSR"},{"key":"CR11","unstructured":"M. Sipser, Private communication, 1991."},{"key":"CR12","unstructured":"M. Sipser, A topological view of some problems in complexity theory. InColloq. math. Soc. J\ufffdnos Bolyai 44 (1985), 387?391."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity. InProc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 77?82.","DOI":"10.1145\/28395.28404"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"L.G. Valiant, Graph-theoretic arguments in low level complexity. InProc. Sixth Conf. Math. Foundations of Computer Science, Lecture Notes in Computer Science, 1977, Springer-Verlag, 162?176.","DOI":"10.1007\/3-540-08353-7_135"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Separating the polynomial time hierarchy by oracles. InProc. Twentysixth Ann. IEEE Symp. Found. Comput. Sci., 1985, 1?10.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268140.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01268140\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01268140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T14:13:47Z","timestamp":1556633627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01268140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01268140"],"URL":"https:\/\/doi.org\/10.1007\/bf01268140","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}