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
[PDF (398K)]    [PS (2333K)]    [PS.GZ (450K)]
[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.