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).
