{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:35Z","timestamp":1725483755461},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_18","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"222-231","source":"Crossref","is-referenced-by-count":3,"title":["Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication"],"prefix":"10.1007","author":[{"given":"Beate","family":"Bollig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M. (1999). A non-linear time lower bound for Boolean branching programs. Proc. of 40th FOCS, 60\u201370.","DOI":"10.1109\/SFFCS.1999.814578"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","volume":"37","author":"N. Alon","year":"1988","unstructured":"Alon, N. and Maass, W. (1988). Meanders and their applications in lower bound arguments. Journal of Computer and System Sciences 37, 118\u2013129.","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR3","unstructured":"Bollig, B., Sauerhoff, M., Sieling, D., and Wegener, I. (1993). Read-k times ordered binary decision diagrams. Efficient algorithms in the presence of null chains. Tech. Report 474, Univ. Dortmund."},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/inco.1998.2710","volume":"143","author":"B. Bollig","year":"1998","unstructured":"Bollig, B. and Wegener, I. (1998). Completeness and non-completeness results with respect to read-once projections. Information and Computation 143, 24\u201333.","journal-title":"Information and Computation"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s002240000128","volume":"32","author":"B. Bollig","year":"1999","unstructured":"Bollig, B. and Wegener, I. (1999). Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory of Computing Systems 32, 487\u2013503.","journal-title":"Theory of Computing Systems"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A., and Smolensky, R. (1993). On lower bounds for read-k-times branching programs. Comput. Complexity 3, 1\u201318.","journal-title":"Comput. Complexity"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R. E. Bryant","year":"1986","unstructured":"Bryant, R. E. (1986). Graph-based algorithms for Boolean manipulation. IEEE Trans. on Computers 35, 677\u2013691.","journal-title":"IEEE Trans. on Computers"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"R. E. Bryant","year":"1991","unstructured":"Bryant, R. E. (1991). On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. on Computers 40, 205\u2013213.","journal-title":"IEEE Trans. on Computers"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0020-0190(94)00094-8","volume":"51","author":"J. Gergov","year":"1994","unstructured":"Gergov, J. (1994). Time-space trade-offs for integer multiplication on various types of input oblivious sequential machines. Information Processing Letters 51, 265\u2013269.","journal-title":"Information Processing Letters"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1109\/12.324545","volume":"43","author":"J. Gergov","year":"1994","unstructured":"Gergov, J. and Meinel, C. (1994). Efficient Boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. on Computers 43, 1197\u20131209.","journal-title":"IEEE Trans. on Computers"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J. (1997). Communication Complexity and Parallel Computing. Springer.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"18_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/3-540-46541-3_12","volume-title":"Proc. of 17th STACS","author":"J. Hromkovi\u010d","year":"2000","unstructured":"Hromkovi\u010d, J. and Sauerhoff, M. (2000). Communications with restricted nondeterminism and applications to branching program complexity. Proc. of 17th STACS, Lecture Notes in Computer Science 1770, 145\u2013156."},{"key":"18_CR13","unstructured":"Jain, J., Abadir, M., Bitner, J., Fussell, D. S., and Abraham, J. A. (1992). Functional partitioning for verification and related problems. Brown\/MIT VLSI Conference, 210\u2013226."},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E. and Nisan, N. (1997). Communication Complexity. Cambridge University Press.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"18_CR15","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0890-5401(90)90046-K","volume":"85","author":"C. Meinel","year":"1990","unstructured":"Meinel, C. (1990). Polynomial size \u03a9-branching programs and their computational power. Information and Computation 85, 163\u2013182.","journal-title":"Information and Computation"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1137\/S0097539795290349","volume":"28","author":"S. Ponzio","year":"1998","unstructured":"Ponzio, S. (1998). A lower bound for integer multiplication with read-once branching programs. SIAM Journal on Computing 28, 798\u2013815.","journal-title":"SIAM Journal on Computing"},{"key":"18_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/3-540-46691-6_28","volume-title":"Proc. of 19th FST & TCS","author":"M. Sauerhoff","year":"1999","unstructured":"Sauerhoff, M. (1999). Computing with restricted nondeterminism: The dependence of the OBDD size on the number of nondeterministic variables. Proc. of 19th FST & TCS, Lecture Notes in Computer Science 1738, 342\u2013355."},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Savick\u00fd, P. and Sieling, D. (2000). A hierarchy result for read-once branching programs with restricted parity nondeterminism. Preprint.","DOI":"10.1007\/3-540-44612-5_60"},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0304-3975(94)00078-W","volume":"141","author":"D. Sieling","year":"1995","unstructured":"Sieling, D. and Wegener, I. (1995). Graph driven BDDs-a new data structure for Boolean functions. Theoretical Computer Science 141, 283\u2013310.","journal-title":"Theoretical Computer Science"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Thathachar, J. (1998). On separating the read-k-times branching program hierarchy. Proc. of 30th Ann. ACM Symposium on Theory of Computing (STOC), 653\u2013662.","DOI":"10.1145\/276698.276881"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Wegener, I. (1987). The Complexity of Boolean Functions Wiley-Teubner.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"18_CR22","unstructured":"Wegener, I. (2000). Branching Programs and Binary Decision Diagrams-Theory and Applications SIAM Monographs on Discrete Mathematics and Applications. In print."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T18:41:34Z","timestamp":1556390494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}