pdf icon
Volume 15 (2019) Article 2 pp. 1-31
Time Bounds for Streaming Problems
Received: March 13, 2017
Revised: January 11, 2018
Published: September 7, 2019
Download article from ToC site:
[PDF (398K)] [PS (2333K)] [Source ZIP]
Keywords: lower bounds, cell probe, streaming algorithms, online algorithms
ACM Classification: F.2.2
AMS Classification: 68Q17

Abstract: [Plain Text Version]

$ $

We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model.

  • We first consider online convolution where the task is to compute the inner product between a fixed $n$-dimensional vector and a vector of the $n$ most recent values from a stream. One symbol of the stream arrives at a time and then each output symbol must be computed before the next input symbol arrives.

  • Next we show bounds for online multiplication of two $n$-digit numbers where one of the multiplicands is known in advance and the other arrives one digit at a time, starting from the lower-order end. When a digit arrives, the task is to compute a single new digit from the product before the next digit arrives.

  • Finally we look at the online Hamming distance problem where the Hamming distance is computed instead of the inner product.

For each of these three problems, we give a lower bound of $\Omega\left(({\delta}/{w})\log n\right)$ time on average per output symbol, where $\delta$ is the number of bits needed to represent an input symbol and $w$ is the cell or word size. We argue that these bounds are in fact tight within the cell probe model.


Preliminary versions of these results first appeared in the Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), 2011 and the Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.