{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:59:25Z","timestamp":1775282365612,"version":"3.50.1"},"reference-count":21,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1987,10,1]],"date-time":"1987-10-01T00:00:00Z","timestamp":560044800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":9421,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1987,10]]},"DOI":"10.1016\/0022-0000(87)90010-9","type":"journal-article","created":{"date-parts":[[2003,12,4]],"date-time":"2003-12-04T12:01:00Z","timestamp":1070539260000},"page":"153-162","source":"Crossref","is-referenced-by-count":10,"title":["A lower bound for read-once-only branching programs"],"prefix":"10.1016","volume":"35","author":[{"given":"L\u00e1szl\u00f3","family":"Babai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e9ter","family":"Hajnal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Endre","family":"Szemer\u00e9di","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0022-0000(87)90010-9_BIB1","doi-asserted-by":"crossref","unstructured":"N. Alon and R. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, in press.","DOI":"10.1007\/BF02579196"},{"issue":"No. 5","key":"10.1016\/0022-0000(87)90010-9_BIB2","first-page":"1033","article-title":"On a method of obtaining lower bounds for the complexity of individual monotone functions","volume":"282","author":"Andreev","year":"1985","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0022-0000(87)90010-9_BIB3","series-title":"Proceedings, 18th ACM Symp. Theory of Comput.","first-page":"169","article-title":"Limits on the power of concurrent-write parallel machines","author":"Beame","year":"1986"},{"key":"10.1016\/0022-0000(87)90010-9_BIB4","doi-asserted-by":"crossref","unstructured":"P. Beane and S. Cook, 1985, private communication.","DOI":"10.1007\/978-1-349-17825-4_2"},{"key":"10.1016\/0022-0000(87)90010-9_BIB5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0022-0000(81)90037-4","article-title":"A timespace tradeoff for sorting on nonoblivious machines","volume":"22","author":"Borodin","year":"1981","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/0022-0000(87)90010-9_BIB6","unstructured":"S. Fortune, J. Hopcroft, and E. M. Schmidt, \u201cThe Complexity of Equivalence and Containment Free Single Variable Program Schemes,\u201d Cornell Univ. TR77-310."},{"key":"10.1016\/0022-0000(87)90010-9_BIB7","series-title":"Ramsey Theory","author":"Graham","year":"1980"},{"key":"10.1016\/0022-0000(87)90010-9_BIB8","series-title":"Proceedings, 18th ACM Symp. Theory of Comput.","first-page":"6","article-title":"Improved lower bounds for small depth circuits","author":"Hastad","year":"1986"},{"key":"10.1016\/0022-0000(87)90010-9_BIB9","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","article-title":"Representation of switching functions by binary decision programs","volume":"38","author":"Lee","year":"1959","journal-title":"Bell System Tech. J."},{"key":"10.1016\/0022-0000(87)90010-9_BIB10","series-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1979"},{"key":"10.1016\/0022-0000(87)90010-9_BIB11","article-title":"A Fast Algorithm for the String Editing Problem and Decision Graph Complexity","author":"Masek","year":"1976"},{"issue":"No. 4","key":"10.1016\/0022-0000(87)90010-9_BIB12_1","first-page":"765","article-title":"On a Boolean function","volume":"169","author":"Ne\u010diporuk","year":"1966","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0022-0000(87)90010-9_BIB12_2","first-page":"999","volume":"7","author":"Ne\u010diporuk","year":"1966","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/0022-0000(87)90010-9_BIB13","series-title":"Proceedings, Conf. Mathematical Foundations of Computer Science 1984","first-page":"480","article-title":"A lower bound on complexity of branching programs","volume":"Vol. 176","author":"Pudl\u00e1k","year":"1984"},{"key":"10.1016\/0022-0000(87)90010-9_BIB14","first-page":"798","article-title":"Lower bounds for the monotone complexity of some Boolean functions","volume":"281","author":"Razborov","year":"1985","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"No. 6","key":"10.1016\/0022-0000(87)90010-9_BIB15","article-title":"A lower bound for the monotone network complexity of the logical permanent","volume":"37","author":"Razaorov","year":"1985","journal-title":"Mat. Zametki"},{"key":"10.1016\/0022-0000(87)90010-9_BIB16","series-title":"The Complexity of Computing","author":"Savage","year":"1976"},{"key":"10.1016\/0022-0000(87)90010-9_BIB17","article-title":"On the Complexity of Branching Programs and Decision Trees for Clique Functions","author":"Wegener","year":"1984","journal-title":"Universit\u00e4t Frankfurt, Fachbereich Informatik, Int. Rept. 5\/84"},{"key":"10.1016\/0022-0000(87)90010-9_BIB18","series-title":"Proceedings, 24th IEEE Found. of Comput. Sci.","first-page":"420","article-title":"Lower bounds by probabilistic arguments","author":"Yao","year":"1983"},{"key":"10.1016\/0022-0000(87)90010-9_BIB19","series-title":"Proceedings, 26th IEEE Found. of Comput. Sci.","first-page":"1","article-title":"Separating the Polynomial-time hierarchy by oracles","author":"Yao","year":"1985"},{"key":"10.1016\/0022-0000(87)90010-9_BIB20","series-title":"Proceedings, Conf. on Mathematical Foundations of Computer Science","first-page":"562","article-title":"An exponential lower bound for one-time-only branching Programs","volume":"Vol. 176,","author":"Z\u00e1k","year":"1984"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0022000087900109?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0022000087900109?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T13:53:34Z","timestamp":1550325214000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0022000087900109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,10]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1987,10]]}},"alternative-id":["0022000087900109"],"URL":"https:\/\/doi.org\/10.1016\/0022-0000(87)90010-9","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1987,10]]}}}