Lower Bounds for Streaming Problems
- Speaker: Dr Markus Jalsenius, Department of Computer Science, University of Bristol
- Date: Wednesday, 20 March 2013 from 16:30 to 17:30
- Location: Room 160, Birkbeck Main Building
Time lower bounds for dynamic data structures have historically proven hard to show. The very first log(n) lower bound was obtained as recently as in 2004. Building on the lower bound techniques from data structures, we have proved the very first time lower bounds for streaming problems. In this talk I will consider the following 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 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. I will argue why our lower bounds are unlikely to be improved and how they relate to the currently known upper bounds.
It is joint work with Raphael Clifford and Benjamin Sach.