Tata Institute of Fundamental Research
Streaming Algorithm
Student Seminar
Speaker:
Dr. A. V. Sreejith (School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Mumbai 400005)
Organiser:
Suneel Sarswat
Date:
Friday, 18 Oct 2013, 16:00 to 17:30
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: In the streaming model, we look at a sequence of elements where each element comes from the set . Our aim is to compute some function on these numbers, but using very "little" space. The best algorithm would be one which uses space.In the course of the talk we will show that finding the highest element in a stream can be done better than 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).
| Speaker: | Dr. A. V. Sreejith (School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road Mumbai 400005) |
| Organiser: | Suneel Sarswat |
| Date: | Friday, 18 Oct 2013, 16:00 to 17:30 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: In the streaming model, we look at a sequence of elements where each element comes from the set . Our aim is to compute some function on these numbers, but using very "little" space. The best algorithm would be one which uses space.In the course of the talk we will show that finding the highest element in a stream can be done better than 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).