BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T092716Z
UID:Seminar-dept-299@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20121106T160000
DTEND:20121106T170000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Markus Jalsenius: Lower Bounds for Streaming Problems\n\nWe 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.\n\n\nWe 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.\n\n\n\nThis 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\n\nhttp://arxiv.org/abs/1101.0768 and http://arxiv.org/abs/1207.1885\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=299
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR