Lower Bounds for Streaming Problems

6^th November 2012, 16:00 Ashton Lecture Theatre
Dr. Markus Jalsenius
Department of Computer Science
University of Bristol
UK

Abstract

We demonstrate time lower bounds for three fundamental streaming problems: computing the convolution/cross-correlation (i.e. the inner product) between a fixed vector of length n and the last n numbers of a stream, computing the Hamming distance between a fixed string of length n and the last n symbols of a stream, as well as multiplication of two n digit numbers (here the digits of a number arrive one at a time and the corresponding digit of the product has to be outputted before the next digit arrives). For these problems we obtain lower bounds of log(n) time on average per output. The lower bounds are given in the cell-probe model (hence hold in the RAM model) and hold under randomisation and amortisation. The lower bounds are unconditional, in particular there are no space constraints.

We obtain the bounds by applying lower bound techniques from data structures (in a non-trivial way). In the talk I will give a brief introduction to lower bounds. I will argue why our lower bounds are unlikely to be improved and how they relate to the currently known upper bounds, as well as highlight the difficulties in deriving lower bounds (for other streaming problems). The main part of the talk concerns the actual lower bound proofs, where I will explain, in the context of streaming, how information theoretic arguments lead to logarithmic lower bounds.

This work appeared in ICALP'11 and (to come) SODA'13. It is joint work with Raphael Clifford and Benjamin Sach. Details can be found at
http://arxiv.org/abs/1101.0768 and http://arxiv.org/abs/1207.1885

Additional Materials

• http://arxiv.org/abs/1207.1885