Time bounds for streaming problems

Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Research output: Contribution to journalArticle (Academic Journal)

55 Downloads (Pure)

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 Ω((δ/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.

Original languageEnglish
Article number2
Pages (from-to)1-31
Number of pages31
JournalTheory of Computing
Volume15
DOIs
Publication statusPublished - 7 Sep 2019

Keywords

  • Cell probe
  • Lower bounds
  • Online algorithms
  • Streaming algorithms

Fingerprint Dive into the research topics of 'Time bounds for streaming problems'. Together they form a unique fingerprint.

  • Cite this