{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:55Z","timestamp":1763468035015},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"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-22006-7_50","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"593-604","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model"],"prefix":"10.1007","author":[{"given":"Rapha\u00ebl","family":"Clifford","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Jalsenius","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"50_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-540-69068-9_15","volume-title":"Combinatorial Pattern Matching","author":"R. Clifford","year":"2008","unstructured":"Clifford, R., Efremenko, K., Porat, B., Porat, E.: A black box for online approximate pattern matching. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 143\u2013151. Springer, Heidelberg (2008)"},{"issue":"1","key":"50_CR2","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jda.2010.09.005","volume":"9","author":"R. Clifford","year":"2011","unstructured":"Clifford, R., Sach, B.: Pattern matching in pseudo real-time. Journal of Discrete Algorithms\u00a09(1), 67\u201381 (2011)","journal-title":"Journal of Discrete Algorithms"},{"key":"50_CR3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1515\/crll.1960.203.47","volume":"203","author":"D.E. Daykin","year":"1960","unstructured":"Daykin, D.E.: Distribution of bordered persymmetric matrices in a finite field. Journal f\u00fcr die reine und angewandte Mathematik\u00a0203, 47\u201354 (1960)","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"50_CR4","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Stockmeyer, L.J.: Fast on-line integer multiplication. In: STOC 1973: Proc. 5th Annual ACM Symposium Theory of Computing, pp. 67\u201372 (1973)","DOI":"10.1145\/800125.804037"},{"issue":"2","key":"50_CR5","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1137\/0207012","volume":"7","author":"M.L. Fredman","year":"1978","unstructured":"Fredman, M.L.: Observations on the complexity of generating quasi-gray codes. SIAM Journal on Computing\u00a07(2), 134\u2013146 (1978)","journal-title":"SIAM Journal on Computing"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Saks, M.: The cell probe complexity of dynamic data structures. In: STOC 1989: Proc. 21st Annual ACM Symposium Theory of Computing, pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"issue":"1","key":"50_CR7","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1145\/322234.322244","volume":"28","author":"Z. Galil","year":"1981","unstructured":"Galil, Z.: String matching in real time. Journal of the ACM\u00a028(1), 134\u2013149 (1981)","journal-title":"Journal of the ACM"},{"key":"50_CR8","doi-asserted-by":"crossref","unstructured":"Kaltofen, E., Lobo, A.: On rank properties of Toeplitz matrices over finite fields. In: ISSAC 1996: Proc. of the 1996 International Symposium on Symbolic and Algebraic Computation, pp. 241\u2013249 (1996)","DOI":"10.1145\/236869.237081"},{"key":"50_CR9","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"M. Minsky","year":"1969","unstructured":"Minsky, M., Papert, S.: Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge (1969)"},{"key":"50_CR10","first-page":"97","volume-title":"Proceedings of SIAM-AMS","author":"M.S. Paterson","year":"1974","unstructured":"Paterson, M.S., Fischer, M.J., Meyer, A.R.: An improved overlap argument for on-line multiplication. In: Proceedings of SIAM-AMS, vol.\u00a07, pp. 97\u2013111. Amer. Math. Soc., Providence (1974)"},{"key":"50_CR11","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Lower Bound Techniques for Data Structures. PhD thesis, Massachusetts Institute of Technology (2008)","DOI":"10.1109\/FOCS.2008.69"},{"key":"50_CR12","unstructured":"P\u01cetra\u015fcu, M., Demaine, E.D.: Tight bounds for the partial-sums problem. In: SODA 2004: Proc. 15th ACM\/SIAM Symposium on Discrete Algorithms, pp. 20\u201329 (2004)"},{"issue":"4","key":"50_CR13","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M. P\u0103tra\u015fcu","year":"2006","unstructured":"P\u0103tra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing\u00a035(4), 932\u2013963 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"50_CR14","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity. In: FOCS 1977: Proc. 18th Annual Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"},{"issue":"3","key":"50_CR15","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C.-C. Yao","year":"1981","unstructured":"Yao, A.C.-C.: Should tables be sorted? Journal of the ACM\u00a028(3), 615\u2013628 (1981)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T14:39:20Z","timestamp":1686148760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}