{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:08:21Z","timestamp":1725574101704},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642183805"},{"type":"electronic","value":"9783642183812"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-18381-2_11","type":"book-chapter","created":{"date-parts":[[2011,1,4]],"date-time":"2011-01-04T11:01:51Z","timestamp":1294138911000},"page":"135-145","source":"Crossref","is-referenced-by-count":0,"title":["Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size"],"prefix":"10.1007","author":[{"given":"Beate","family":"Bollig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Gill\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-63165-8_177","volume-title":"Automata, Languages and Programming","author":"F. Ablayev","year":"1997","unstructured":"Ablayev, F.: Randomization and nondeterminism are incomparable for ordered read-once branching programs. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 195\u2013202. Springer, Heidelberg (1997)"},{"key":"11_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-61440-0_141","volume-title":"Automata, Languages and Programming","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F., Karpinski, M.: On the power of randomized ordered branching programs. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 348\u2013356. Springer, Heidelberg (1996)"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/S0890-5401(03)00118-4","volume":"186","author":"F. Ablayev","year":"2003","unstructured":"Ablayev, F., Karpinski, M.: A lower bound for integer multiplication on randomized ordered read-once branching programs. Information and Computation\u00a0186(1), 78\u201389 (2003)","journal-title":"Information and Computation"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-540-79228-4_27","volume-title":"Theory and Applications of Models of Computation","author":"B. Bollig","year":"2008","unstructured":"Bollig, B.: On the OBDD complexity of the most significant bit of integer multiplication. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 306\u2013317. Springer, Heidelberg (2008)"},{"key":"11_CR5","first-page":"78","volume":"98","author":"B. Bollig","year":"2009","unstructured":"Bollig, B.: Integer multiplication and the complexity of binary decision diagrams. EATCS Bulletin\u00a098, 78\u2013106 (2009)","journal-title":"EATCS Bulletin"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-642-00982-2_18","volume-title":"Language and Automata Theory and Applications","author":"B. Bollig","year":"2009","unstructured":"Bollig, B.: Larger lower bounds on the OBDD complexity of integer multiplication. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 212\u2013223. Springer, Heidelberg (2009)"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/978-3-642-12200-2_24","volume-title":"LATIN 2010: Theoretical Informatics","author":"B. Bollig","year":"2010","unstructured":"Bollig, B.: A larger lower bound on the OBDD complexity of the most significant bit of multiplication. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 255\u2013266. Springer, Heidelberg (2010)"},{"key":"11_CR8","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":"11_CR9","doi-asserted-by":"crossref","unstructured":"Bollig, B., Woelfel, P.: A read-once branching program lower bound of \u03a9(2 n\/4) for integer multiplication using universal hashing. In: Proc. of 33rd STOC, pp. 419\u2013424 (2001)","DOI":"10.1145\/380752.380835"},{"key":"11_CR10","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 function manipulation. IEEE Trans. on Computers\u00a035, 677\u2013691 (1986)","journal-title":"IEEE Trans. on Computers"},{"key":"11_CR11","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":"11_CR12","doi-asserted-by":"crossref","unstructured":"De, A., Kurur, P., Saha, C., Sapthariski, R.: Fast integer multiplication using modular arithmetic. In: Proc.of 40th STOC, pp. 499\u2013506 (2008)","DOI":"10.1145\/1374376.1374447"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: Faster integer multiplication. In: Proc. of 39th STOC, pp. 57\u201366 (2007)","DOI":"10.1145\/1250790.1250800"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Hajnal, A., Maass, W., Pudl\u00e1k, P., Szegedy, M., Tur\u00e1n, G.: Threshold circuits of bounded depth. In: Proc. 28th FOCS 1987, pp. 99\u2013110 (1987)","DOI":"10.1109\/SFCS.1987.59"},{"key":"11_CR15","doi-asserted-by":"publisher","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)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s000370050018","volume":"8","author":"I. Kremer","year":"1999","unstructured":"Kremer, I., Nisan, N., Ron, D.: On Randomized One-Round Communication Complexity. Computational Complexity\u00a08(1), 21\u201349 (1999)","journal-title":"Computational Complexity"},{"key":"11_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"1","key":"11_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P.B. Miltersen","year":"1998","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. Journal of Computer and System Science\u00a057(1), 37\u201349 (1998)","journal-title":"Journal of Computer and System Science"},{"key":"11_CR19","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":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BFb0028553","volume-title":"STACS 98","author":"M. Sauerhoff","year":"1998","unstructured":"Sauerhoff, M.: Lower bounds for randomized read-k-times branching programs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 103\u2013115. Springer, Heidelberg (1998)"},{"key":"11_CR21","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 35th STOC, pp. 186\u2013195 (2003)","DOI":"10.1145\/780569.780571"},{"key":"11_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation gro\u00dfer Zahlen. Computing\u00a07, 281\u2013292 (1971)","journal-title":"Computing"},{"issue":"3","key":"11_CR23","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/j.jcss.2007.06.016","volume":"74","author":"P. Sen","year":"2008","unstructured":"Sen, P., Venkatesh, S.: Lower bounds for predecessor searching in the cell probe model. Journal of Computer and System Sciences\u00a074(3), 364\u2013385 (2008)","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR24","unstructured":"Smirnov, D.: Shannon\u2019s information methods for lower bounds for probabilistic communication complexity. Master\u2019s thesis, Moskow University (1988)"},{"key":"11_CR25","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":"11_CR26","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"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2011: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-18381-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T11:02:40Z","timestamp":1559905360000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-18381-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642183805","9783642183812"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-18381-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}