Event calendar file
School of Technology and Computer Science Seminars
Streaming Algorithm
by Dr. A.V. Sreejith (School of Technology and Computer Science, TIFR)
Friday, October 18, 2013
from
to
(Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
at Colaba Campus ( D-405 (D-Block Seminar Room) )
| Description |
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).
|
