{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:25:30Z","timestamp":1774589130996,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540614401","type":"print"},{"value":"9783540685807","type":"electronic"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61440-0_141","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:38:02Z","timestamp":1330292282000},"page":"348-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["On the power of randomized branching programs"],"prefix":"10.1007","author":[{"given":"Farid","family":"Ablayev","sequence":"first","affiliation":[]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-58140-5_1","volume":"813","author":"F. Ablayev","year":"1994","unstructured":"F. Ablayev, Lower bounds for probabilistic space complexity: communication-automata approach, in Proceedings of the LFCS'94, Lecture Notes in Computer Science, Springer-Verlag, 813, (1994), 1\u20137.","journal-title":"Proceedings of the LFCS'94, Lecture Notes in Computer Science, Springer-Verlag"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"L. Adelman, Two theorems on random polynomial time, in Proceedings of the 19-th FOCS, (1978), 75\u201383.","DOI":"10.1109\/SFCS.1978.37"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and M. Ben-Or, A theorem on randomized constant depth circuits, in Proceedings of the 16-th STOC, (1984), 471\u2013474.","DOI":"10.1145\/800057.808715"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennet","year":"1981","unstructured":"C. Bennet and J. Gill, Relative to a random oracle A, P A \u2260 NPA \u2260 co \u2014 NPA with probability 1, SIAM J. Comput, 10, (1981), 96\u2013113.","journal-title":"SIAM J. Comput"},{"key":"29_CR5","unstructured":"B. Boiling, M. Sauerhoff, D. Sieling, and I. Wegener, On the power of different types of restricted branching programs, ECCC Reports 1994, TR94-025."},{"key":"29_CR6","first-page":"757","volume-title":"in Handbook of Theoretical Computer Science, Vol A: Algorithms and Complexity","author":"R. Boppana","year":"1990","unstructured":"R. Boppana and M. Sipser, The complexity of finite functions, in Handbook of Theoretical Computer Science, Vol A: Algorithms and Complexity, MIT Press and Elsevier, The Netherlands, 1990, ed. J Van Leeuwen, 757\u2013804."},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov, and R. Smolensky, On lower bounds for read-k-times branching programs, Computational Complexity, 3, (1993), 1\u201318.","journal-title":"Computational Complexity"},{"key":"29_CR8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-57568-5_251","volume":"762","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, Time-space tradeoffs (getting closer to barrier?), in Proceedings of the ISAAC'93, Lecture Notes in Computer Science, Springer-Verlag, 762, (1993), 209\u2013220.","journal-title":"in Proceedings of the ISAAC'93, Lecture Notes in Computer Science, Springer-Verlag"},{"issue":"No.3","key":"29_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"R. Bryant","year":"1992","unstructured":"R. Bryant, Symbolic boolean manipulation with ordered binary decision diagrams, ACM Computing Surveys, 24, No. 3, (1992), 293\u2013318.","journal-title":"ACM Computing Surveys"},{"key":"29_CR10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-09526-8_5","volume":"74","author":"R. Frevalds","year":"1979","unstructured":"R. Frevalds, Fast probabilistic algorithms, in Proceedings of the Conference Mathematical Foundation of Computer Science 1979, Lecture Notes in Computer Science, Springer-Verlag, 74, (1979), 57\u201369.","journal-title":"Lecture Notes in Computer Science, Springer-Verlag"},{"key":"29_CR11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/3-540-60084-1_73","volume":"944","author":"R. Freivalds","year":"1995","unstructured":"R. Freivalds and M. Karpinski, Lower time bounds for randomized computation, in Proceedings of the ICALP'95, Lecture Notes in Computer Science, Springer-Verlag, 944, (1995), 183\u2013195.","journal-title":"Proceedings of the ICALP'95, Lecture Notes in Computer Science, Springer-Verlag"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(91)90072-A","volume":"91","author":"M. Krause","year":"1991","unstructured":"M. Krause, Lower bounds for depth-restricted branching programs, Information and Computation, 91, (1991), 1\u201314.","journal-title":"Information and Computation"},{"key":"29_CR13","doi-asserted-by":"crossref","first-page":"985","DOI":"10.1002\/j.1538-7305.1959.tb01585.x","volume":"38","author":"C. Y. Lee","year":"1959","unstructured":"C. Y. Lee, Representation of switching circuits by binary-decision programs, Bell System Technical Journal, 38, (1959), 985\u2013999.","journal-title":"Bell System Technical Journal"},{"key":"29_CR14","unstructured":"L. Lovasz, Communication complexity: a survey, in \u201cPaths, Flows and VLSI Layout\u201d, Karte, Lovasz, Proemel, Schrijver Eds., Springer-Verlag (1990), 235\u2013266."},{"key":"29_CR15","volume-title":"M.Sc. Thesis","author":"W. Masek","year":"1976","unstructured":"W. Masek, A fast algorithm for the string editing problem and decision graph complexity, M.Sc. Thesis, Massachusetts Institute of Technology, Cambridge, May 1976."},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"S. Ponzio, A lower bound for integer multiplication with read-once branching programs, Proceedings of the 27-th STOC, (1995), 130\u2013139.","DOI":"10.1145\/225058.225098"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"A. Razborov, Lower bounds for deterministic and nondeterministic branching programs, in Proceedings of the FCT'91, Lecture Notes in Computer Science, Springer-Verlag, 529, (1991), 47\u201360.","DOI":"10.1007\/3-540-54458-5_49"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"J. Simon and M. Szegedy, A new lower bound theorem for read-only-once branching programs and its applications, Advances in Computational Complexity Theory, ed. Jin-Yi Cai, DIMACS Series, 13, AMS (1993), 183\u2013193.","DOI":"10.1090\/dimacs\/013\/11"},{"key":"29_CR19","volume-title":"The complexity of Boolean functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener, The complexity of Boolean functions. Wiley-Teubner Series in Comp. Sci., New York-Stuttgart, 1987."},{"key":"29_CR20","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0012-365X(95)90790-R","volume":"136","author":"I. Wegener","year":"1994","unstructured":"I. Wegener, Efficient data structures for boolean functions, Discrete Mathematics, 136, (1994), 347\u2013372.","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61440-0_141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:18:42Z","timestamp":1742599122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61440-0_141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614401","9783540685807"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-61440-0_141","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}