Theory of Computing
-------------------
Title     : Time Bounds for Streaming Problems
Authors   : Raphael Clifford, Markus Jalsenius, and Benjamin Sach
Volume    : 15
Number    : 2
Pages     : 1-31
URL       : https://theoryofcomputing.org/articles/v015a002

Abstract
--------

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((\delta/w)\log n)$ 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.