{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T06:17:46Z","timestamp":1738217866033,"version":"3.34.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540792277"},{"type":"electronic","value":"9783540792284"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_27","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"306-317","source":"Crossref","is-referenced-by-count":9,"title":["On the OBDD Complexity of the Most Significant Bit of Integer Multiplication"],"prefix":"10.1007","author":[{"given":"Beate","family":"Bollig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"1224","DOI":"10.1016\/j.dam.2006.11.010","volume":"155","author":"K. Amano","year":"2007","unstructured":"Amano, K., Maruoka, A.: Better upper bounds on the QOBDD size of integer multiplication. Discrete Applied Mathematics\u00a0155, 1224\u20131232 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1051\/ita:2001113","volume":"35","author":"B. Bollig","year":"2001","unstructured":"Bollig, B.: Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO Theoretical Informatics and Applications\u00a035, 149\u2013162 (2001)","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Bollig, B., Woelfel, P.: A read-once branching program lower bound of \u03a9(2n\/4) for integer multiplication using universal hashing. In: Proc. of 33rd STOC, pp. 419\u2013424 (2001)","DOI":"10.1145\/380752.380835"},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2006.05.035","volume":"362","author":"B. Bollig","year":"2006","unstructured":"Bollig, B., Waack, S., Woelfel, P.: Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication. Theoretical Computer Science\u00a0362, 86\u201399 (2006)","journal-title":"Theoretical Computer Science"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/s00224-004-1130-1","volume":"38","author":"B. Bollig","year":"2005","unstructured":"Bollig, B., Woelfel, P.: A lower bound technique for nondeterministic graph-driven read-once branching programs and its applications. Theory of Computing Systems\u00a038, 671\u2013685 (2005)","journal-title":"Theory of Computing Systems"},{"key":"27_CR6","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.: Graph-based algorithms for Boolean manipulation. IEEE Trans. on Computers\u00a035, 677\u2013691 (1986)","journal-title":"IEEE Trans. on Computers"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"R.E. Bryant","year":"1991","unstructured":"Bryant, R.E.: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. on Computers\u00a040, 205\u2013213 (1991)","journal-title":"IEEE Trans. on Computers"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"F\u00fchrer, M.: Faster integer multiplication. In: Proc. of 39th STOC, pp. 57\u201366 (2007)","DOI":"10.1145\/1250790.1250800"},{"key":"27_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.: Time-space trade-offs for integer multiplication on various types of input oblivious sequential machines. Information Processing Letters\u00a051, 265\u2013269 (1994)","journal-title":"Information Processing Letters"},{"key":"27_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03442-2","volume-title":"Communication Complexity and Parallel Computing","author":"J. Hromkovi\u010d","year":"1997","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)"},{"key":"27_CR11","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1137\/S0097539795290349","volume":"28","author":"S. Ponzio","year":"1998","unstructured":"Ponzio, S.: A lower bound for integer multiplication with read-once branching programs. SIAM Journal on Computing\u00a028, 798\u2013815 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Sauerhoff, M., Woelfel, P.: Time-space trade-off lower bounds for integer multiplication and graphs of arithmetic functions. In: Proc. of 33rd STOC, pp. 186\u2013195 (2003)","DOI":"10.1145\/780542.780571"},{"key":"27_CR14","unstructured":"Sawitzki, D.: Exponential lower bounds on the space complexity of OBDD-based graph algorithms. In: Proc. of LATIN. LNCS, vol. 3831, pp. 471\u2013482 (2005)"},{"issue":"2","key":"27_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0020-0190(93)90202-K","volume":"46","author":"I. Wegener","year":"1993","unstructured":"Wegener, I.: Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions. Information Processing Letters\u00a046(2), 85\u201387 (1993)","journal-title":"Information Processing Letters"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719789"},{"issue":"4","key":"27_CR17","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1016\/j.jcss.2005.05.004","volume":"71","author":"P. Woelfel","year":"2005","unstructured":"Woelfel, P.: New bounds on the OBDD-size of integer multiplication via universal hashing. Journal of Computer and System Science\u00a071(4), 520\u2013534 (2005)","journal-title":"Journal of Computer and System Science"},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Woelfel, P.: On the complexity of integer multiplication in branching programs with multiple tests and in read-once branching programs with limited nondeterminism. In: Proc. of 17th Computational Complexity, pp. 80\u201389 (2002)","DOI":"10.1109\/CCC.2002.1004343"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T23:02:32Z","timestamp":1738191752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_27","relation":{},"subject":[]}}