# Streaming Algorithm

## Speaker:

Dr. A. V. Sreejith

## Affiliation:

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

## Time:

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

## Venue:

• D-405 (D-Block Seminar Room)

## Organisers:

Abstract: In the streaming model, we look at a sequence of elements $\inline {(a_1,a_2,...,a_m)}$ where each element comes from the set $\inline { {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 $\inline {O(log m + log n)}$ space.In the course of the talk we will show that finding the $\inline {k^{th}}$ highest element in a stream can be done better than $\inline {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).