Streaming Algorithm


Dr. A. V. Sreejith


School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Mumbai 400005


Friday, 18 October 2013, 16:00 to 17:30


  • D-405 (D-Block Seminar Room)


Abstract: In the streaming model, we look at a sequence of elements (a_1,a_2,...,a_m) where each element comes from the set {1,2,...,n}. Our aim is to compute some function on these numbers, but using very "little" space. The best algorithm would be one which uses O(log m + log n) space.In the course of the talk we will show that finding the k^{th} highest element in a stream can be done better than O(k log n) bits. We will also look at the space complexity of frequency moments (this work is by Alon,Matias, Szegedy for which they won the Godel prize).