{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T12:51:26Z","timestamp":1767876686468,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1987,3,1]],"date-time":"1987-03-01T00:00:00Z","timestamp":541555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1987,3]]},"DOI":"10.1007\/bf02579196","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T17:14:06Z","timestamp":1174583646000},"page":"1-22","source":"Crossref","is-referenced-by-count":212,"title":["The monotone circuit complexity of boolean functions"],"prefix":"10.1007","volume":"7","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Ravi B.","family":"Boppana","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02579196_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The Design and Analysis of Computer Algorithms, Addison\u2014Wesley, Reading, 1974."},{"key":"BF02579196_CR2","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 (1985), 1033\u20131037 (in Russian). English translation inSov. Math. Dokl. 31 (1985), 530\u2013534.","journal-title":"Dokl. Ak. Nauk. SSSR"},{"key":"BF02579196_CR3","unstructured":"P. A. Bloniarz,The complexity of monotone Boolean functions and an algorithm for finding shortest paths in a graph, Ph. D. Dissertation, Technical Report238, Laboratory for Computer Science, Massachusetts Institute of Technology, 1979."},{"key":"BF02579196_CR4","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(83)90029-4","volume":"28","author":"N. Blum","year":"1984","unstructured":"N. Blum, A Boolean function requiring 3n network size,Theoretical Computer Science 28 (1984), 337\u2013345.","journal-title":"Theoretical Computer Science"},{"key":"BF02579196_CR5","first-page":"46","volume":"16","author":"F. Chung","year":"1984","unstructured":"F. Chung andR. M. Karp,in: Open problems proposed at the NSF Conf. on Complexity Theory, Eugene, Oregon 1984,SIGACT News 16 (1984), 46.","journal-title":"SIGACT News"},{"key":"BF02579196_CR6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","volume":"35","author":"P. Erd\u0151s","year":"1960","unstructured":"P. Erd\u0151s andR. Rado, Intersection theorems for systems of sets,Journal of London Mathematical Society 35 (1960), 85\u201390.","journal-title":"Journal of London Mathematical Society"},{"key":"BF02579196_CR7","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"4","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft andR. M. Karp, Ann 5\/2 algorithm for maximum matching in bipartite graphs,SIAM Journal on Computing 4 (1973), 225\u2013231.","journal-title":"SIAM Journal on Computing"},{"key":"BF02579196_CR8","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02241983","volume":"16","author":"K. Mehlhorn","year":"1976","unstructured":"K. Mehlhorn andZ. Galil, Monotone switching circuits and Boolean matrix product,Computing 16 (1976), 99\u2013111.","journal-title":"Computing"},{"key":"BF02579196_CR9","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"J. Ne\u0161et\u0159il andS. Poljak, On the complexity of the subgraph problem,CMUC 26 (1985), 415\u2013419.","journal-title":"CMUC"},{"key":"BF02579196_CR10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0304-3975(75)90009-2","volume":"1","author":"M. S. Paterson","year":"1975","unstructured":"M. S. Paterson, Complexity of monotone networks for Boolean matrix products,Theoretical Computer Science 1 (1975), 13\u201320.","journal-title":"Theoretical Computer Science"},{"key":"BF02579196_CR11","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1137\/0204027","volume":"4","author":"V. R. Pratt","year":"1974","unstructured":"V. R. Pratt, The power of negative thinking in multiplying Boolean matrices,SIAM Journal on Computing 4 (1974), 326\u2013330.","journal-title":"SIAM Journal on Computing"},{"key":"BF02579196_CR12","first-page":"798","volume":"281","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions,Dokl. Ak. Nauk. SSSR,281, (1985), 798\u2013801 (in Russian). English translation in:Sov. Math. Dokl.,31 (1985), 354\u2013357.","journal-title":"Dokl. Ak. Nauk. SSSR"},{"key":"BF02579196_CR13","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,Mat. Zametki,37 (1985), 887\u2013900 (in Russian). English translation in:Math. Notes of the Academy of Sciences of the USSR 37 (1985), 485\u2013493.","journal-title":"Mat. Zametki"},{"key":"BF02579196_CR14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C. E. Shannon","year":"1949","unstructured":"C. E. Shannon, The synthesis of two-terminal switching circuits,Bell System Technical Journal,28 (1949), 59\u201398.","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"BF02579196_CR15","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1145\/3149.3158","volume":"32","author":"S. Skyum","year":"1985","unstructured":"S. Skyum andL. G. Valiant, A complexity theory based on Boolean algebra,Journal of the ACM,32:2 (1985), 484\u2013502.","journal-title":"Journal of the ACM"},{"key":"BF02579196_CR16","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(84)90111-X","volume":"18","author":"J. Tiekenheinrich","year":"1984","unstructured":"J. Tiekenheinrich, A 4n-lower bound on the monotone network complexity of a one-output Boolean function,Information Processing Letters,18 (1984), 201\u2013202.","journal-title":"Information Processing Letters"},{"key":"BF02579196_CR17","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, Completeness classes in algebra,Proceedings of 11 th ACM Symposium on Theory of Computing, (1979), 249\u2013261.","DOI":"10.1145\/800135.804419"},{"key":"BF02579196_CR18","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0304-3975(89)90084-4","volume":"21","author":"I. Wegener","year":"1982","unstructured":"I. Wegener, Boolean functions whose monotone complexity is of sizen 2\/logn, Theoretical Computer Science,21 (1982), 213\u2013224.","journal-title":"Theoretical Computer Science"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579196.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579196\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T12:44:59Z","timestamp":1558183499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,3]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,3]]}},"alternative-id":["BF02579196"],"URL":"https:\/\/doi.org\/10.1007\/bf02579196","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,3]]}}}