Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 6755))
Included in the following conference series:
1769Accesses
Abstract
We show time lower bounds for both online integer multiplication and convolution in the cell-probe model with word sizew. For the multiplication problem, one pair of digits, each from one of twon digit numbers that are to be multiplied, is given as input at stepi. The online algorithm outputs a single new digit from the product of the numbers before stepi + 1. We give a lower bound of\(\Omega(\frac{\delta}{w} \log n)\) time on average per output digit for this problem where 2δ is the maximum value of a digit. In the convolution problem, we are given a fixed vectorV of lengthn and we consider a stream in which numbers arrive one at a time. We output the inner product ofV and the vector that consists of the lastn numbers of the stream. We show an\(\Omega(\frac{\delta}{w}\log n)\) lower bound for the time required per new number in the stream. All the bounds presented hold under randomisation and amortisation. Multiplication and convolution are central problems in the study of algorithms which also have the widest range of practical applications.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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. 5029, pp. 143–151. Springer, Heidelberg (2008)
Clifford, R., Sach, B.: Pattern matching in pseudo real-time. Journal of Discrete Algorithms 9(1), 67–81 (2011)
Daykin, D.E.: Distribution of bordered persymmetric matrices in a finite field. Journal für die reine und angewandte Mathematik 203, 47–54 (1960)
Fischer, M.J., Stockmeyer, L.J.: Fast on-line integer multiplication. In: STOC 1973: Proc. 5th Annual ACM Symposium Theory of Computing, pp. 67–72 (1973)
Fredman, M.L.: Observations on the complexity of generating quasi-gray codes. SIAM Journal on Computing 7(2), 134–146 (1978)
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–354 (1989)
Galil, Z.: String matching in real time. Journal of the ACM 28(1), 134–149 (1981)
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–249 (1996)
Minsky, M., Papert, S.: Perceptrons: An Introduction to Computational Geometry. MIT Press, Cambridge (1969)
Paterson, M.S., Fischer, M.J., Meyer, A.R.: An improved overlap argument for on-line multiplication. In: Proceedings of SIAM-AMS, vol. 7, pp. 97–111. Amer. Math. Soc., Providence (1974)
Pǎtraşcu, M.: Lower Bound Techniques for Data Structures. PhD thesis, Massachusetts Institute of Technology (2008)
Pǎtraşcu, M., Demaine, E.D.: Tight bounds for the partial-sums problem. In: SODA 2004: Proc. 15th ACM/SIAM Symposium on Discrete Algorithms, pp. 20–29 (2004)
Pătraşcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing 35(4), 932–963 (2006)
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–227 (1977)
Yao, A.C.-C.: Should tables be sorted? Journal of the ACM 28(3), 615–628 (1981)
Author information
Authors and Affiliations
Department of Computer Science, University of Bristol, Bristol, UK
Raphaël Clifford & Markus Jalsenius
- Raphaël Clifford
You can also search for this author inPubMed Google Scholar
- Markus Jalsenius
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
ICE-TCS, School of Computer Science, Reykjavik University, Menntavegur 1, IS 101, Reykjavik, Iceland
Luca Aceto
Fakultät für Informatik, Universität Wien, Universitätsstraße10/9, 1090, Wien, Österreich, Austria
Monika Henzinger
Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic
Jiří Sgall
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Clifford, R., Jalsenius, M. (2011). Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_50
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-22005-0
Online ISBN:978-3-642-22006-7
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative