摘要：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 Ω((δ/w)logn) time on
average per output symbol, where δ 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.
