{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:48:14Z","timestamp":1787503694493,"version":"3.56.0"},"reference-count":20,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1991,3,1]],"date-time":"1991-03-01T00:00:00Z","timestamp":667785600000},"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":8174,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1991,3]]},"DOI":"10.1016\/0890-5401(91)90072-a","type":"journal-article","created":{"date-parts":[[2004,12,16]],"date-time":"2004-12-16T15:34:26Z","timestamp":1103211266000},"page":"1-14","source":"Crossref","is-referenced-by-count":23,"title":["Lower bounds for depth-restricted branching programs"],"prefix":"10.1016","volume":"91","author":[{"given":"Matthias","family":"Krause","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"No. 5","key":"10.1016\/0890-5401(91)90072-A_BIB1","first-page":"1033","article-title":"On a method of obtaining lower bounds to the complexity of individual monotone functions","volume":"282","author":"Andreev","year":"1985","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0890-5401(91)90072-A_BIB2","first-page":"73","article-title":"A method of obtaining superquadratic lower bounds on the complexity of \u03a0-schemes","volume":"6","author":"Andreev","year":"1986","journal-title":"Vestnik. Moscow Un\u01ce. Ser. I Mat. Mech."},{"issue":"No. 1","key":"10.1016\/0890-5401(91)90072-A_BIB3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579196","article-title":"The monotone circuit complexity of Boolean functions","volume":"7","author":"Alon","year":"1987","journal-title":"J. Combinatorika"},{"key":"10.1016\/0890-5401(91)90072-A_BIB4","series-title":"Proceedings ACM STOC","first-page":"30","article-title":"Two lower bounds for branching programs","author":"Ajtai","year":"1986"},{"key":"10.1016\/0890-5401(91)90072-A_BIB5","series-title":"Proceedings 18th ACM STOC","first-page":"1","article-title":"Bounded width-polynomial size branching programs recognize exactly those languages in NC1","author":"Barrington","year":"1986"},{"key":"10.1016\/0890-5401(91)90072-A_BIB6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(83)90029-4","article-title":"A Boolean function requiring 3n network size","volume":"28","author":"Blum","year":"1984","journal-title":"J. Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(91)90072-A_BIB7","series-title":"Proceedings of FCT","first-page":"90","article-title":"Lower bounds on the complexity of one-time-only branching programs","volume":"Vol. 199","author":"Dunne","year":"1985"},{"key":"10.1016\/0890-5401(91)90072-A_BIB8","series-title":"Proceedings, MFCS'86","first-page":"440","article-title":"Lower bounds on the complexity of local circuits","volume":"Vol. 233","author":"Jukna","year":"1986"},{"key":"10.1016\/0890-5401(91)90072-A_BIB9","unstructured":"Krause, M. (to appear), Exponential lower bounds on the complexity of real-time and local branching programs, J. Inform. Process. Cybern. (EIK)."},{"key":"10.1016\/0890-5401(91)90072-A_BIB10","unstructured":"Krause, M. (in preparation), \u201cLower Bounds on the Complexity of Branching Programs\u201d, thesis."},{"key":"10.1016\/0890-5401(91)90072-A_BIB11","first-page":"56","article-title":"Combinational circuits without null chains","volume":"5","author":"Kuznetsov","year":"1981","journal-title":"Izv. Vyssh. Uchebn. Zaved. Mat."},{"key":"10.1016\/0890-5401(91)90072-A_BIB12","series-title":"Proceedings, FCT'87","article-title":"Lower bounds on the complexity of real-time branching programs","volume":"Vol. 278","author":"Kriegel","year":"1987"},{"key":"10.1016\/0890-5401(91)90072-A_BIB13","series-title":"14th STOC","first-page":"30","article-title":"Las Vegas iis better than determinism in VLSI and distributed computing","author":"Mehlhorn","year":"1982"},{"key":"10.1016\/0890-5401(91)90072-A_BIB14","series-title":"Proceedings FCT'87","first-page":"302","article-title":"The power of nondeterminism in polynomial size bounded width branching programs","volume":"Vol. 278","author":"Meinel","year":"1987"},{"key":"10.1016\/0890-5401(91)90072-A_BIB15","first-page":"765","article-title":"A Boolean function","volume":"199","author":"Nechiporuk","year":"1966","journal-title":"Dokl. Akad. Nauk"},{"issue":"No. 3","key":"10.1016\/0890-5401(91)90072-A_BIB16","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0206030","article-title":"A 2.5n-lower bound on the combinational complexity of Boolean functions","volume":"6","author":"Paul","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(91)90072-A_BIB17","series-title":"Space complexity of computation","author":"Pudlak","year":"1983"},{"issue":"No. 6","key":"10.1016\/0890-5401(91)90072-A_BIB18","first-page":"887","article-title":"A lower bound on the monotone complexity of the logical permanent","volume":"37","author":"Razborov","year":"1985","journal-title":"Mat. Zametki"},{"issue":"1988","key":"10.1016\/0890-5401(91)90072-A_BIB19","first-page":"461","article-title":"On the complexity of branching programs and decision trees for clique functions, Interner Bericht der Univ. Frankfurt, 1984","volume":"35","author":"Wegener","year":"1984","journal-title":"Assoc. Comput. Math."},{"key":"10.1016\/0890-5401(91)90072-A_BIB20","series-title":"13th STOC","first-page":"308","article-title":"The entropic limitation of VLSI-computations","author":"Yao","year":"1982"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:089054019190072A?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:089054019190072A?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T20:25:47Z","timestamp":1548879947000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/089054019190072A"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["089054019190072A"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(91)90072-a","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}