{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T04:10:09Z","timestamp":1739851809519,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424949"},{"type":"electronic","value":"9783540446798"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"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":[[2001]]},"DOI":"10.1007\/3-540-44679-6_4","type":"book-chapter","created":{"date-parts":[[2010,2,9]],"date-time":"2010-02-09T17:00:37Z","timestamp":1265734837000},"page":"28-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Separating Oblivious and Non-oblivious BPs"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[]},{"given":"Yasuo","family":"Okabe","sequence":"additional","affiliation":[]},{"given":"Toshiro","family":"Takase","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,7,31]]},"reference":[{"key":"4_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-63165-8_177","volume-title":"\u201cRandomization and nondeterminism are comparable for ordered read once branching programs\u201d","author":"F. Ablayev","year":"1997","unstructured":"F. Ablayev \u201cRandomization and nondeterminism are comparable for ordered read once branching programs\u201d Proc. 24th ICALP, LNCS 1256, 195\u2013202, 1997."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai \u201cA Non-linear Time Lower Bound for Boolean Branching Programs\u201d Proc.40th IEEE FOCS, pp.60\u201369, 1999.","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"4_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/3-540-61440-0_141","volume-title":"\u201cOn the power of randomized branching programs\u201d","author":"F. Ablayev","year":"1996","unstructured":"F. Ablayev and M. Karpinski \u201cOn the power of randomized branching programs\u201d Proc. 23th ICALP, LNCS 1099, 348\u2013356, Paderbon, Germany, 8-12 July 1996."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"N. Alon, and W. Maas, \u201cMeanders, Ramsey theory and lower bound for branching programs\u201d Proc.27th IEEE FOCS, pp.410\u2013417, 1986.","DOI":"10.1109\/SFCS.1986.31"},{"issue":"2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/12.73590","volume":"C-40","author":"R. Bryant","year":"1991","unstructured":"R. Bryant, \u201cOn the complexity of VLSI implementations and graph representations of Boolean function with application to integer multiplication.\u201d IEEE Trans. Computers, C-40(2), pp. 205\u2013213, 1991.","journal-title":"IEEE Trans. Computers"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"L. Babai, N. Nisan, M. Szegedy, \u201cMaltiparty protocols, pseudorandom generators for logspace, and time-space trade-offs\u201d J. Computer System Sciences 45, pp. 204\u2013232, 1992.","journal-title":"J. Computer System Sciences"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov, R. Smolensky, \u201cOn lower-bounds for read-k-times branching programs\u201d Computational Complexity, 3, pp. 1\u201318, 1993.","journal-title":"Computational Complexity"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"R. Boppana and M. Sipser \u201cThe complexity of finite functions\u201d In handbook of Theoretical Computer Science (Volume A), Ed. Jan van Leeuwen. Elsevier and MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"4_CR9","unstructured":"B. Bolling, M. Sauerho., D. Sieling, and I. Wegener, \u201cHierarchy theorems for kOBDDs and kIBDDs.\u201d Theoretical Computer Science, 1996."},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"P. Beame, M. Saks and J. Thathachar, \u201cTime-Space Tradeoffs for Branching programs,\u201d Proc. 39th IEEE FOCS, pp.254\u2013263,1998.","DOI":"10.1109\/SFCS.1998.743453"},{"key":"4_CR11","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 \u201cLower Bounds for Depth-Restricted Branching Programs,\u201d Information and Computation 91, pp. 1\u201314, 1991.","journal-title":"Information and Computation"},{"key":"4_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1007\/BFb0029991","volume-title":"Proc. MFCS97","author":"P. Savicky","year":"1997","unstructured":"P. Savicky and S. Zak, \u201cA Hierarchy for (1,+k)-Branching Programs with Respect to k,\u201d Proc. MFCS97 (LNCS 1295), pp478\u2013487, 1997."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"J. Thathachar, \u201cOn separating the read-k-times branching program hierarchy\u201d Proc. 30th ACM STOC, 1998.","DOI":"10.1145\/276698.276881"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44679-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T03:33:29Z","timestamp":1739849609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44679-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424949","9783540446798"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-44679-6_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"31 July 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}