Streaming algorithms deal with computing useful properties of input data under the assumptions that the size of the data is much larger than the amount of space available for processing it, and re-reading the input data is computationally expensive. Over the last two decades the area of streaming algorithms has seen rapid progress. There are many mathematically beautiful results, and practically useful contributions such as computing frequency moments or histograms of input data. The literature is vast and rapidly growing. This talk will lay down a reading plan for a "streaming algorithm enthusiast". The talk will consist of two sections. In the first section, I will discuss the sketching and sampling based algorithms for computing frequency moments of massive input data. In the second section, I will discuss streaming algorithms for computing properties of large graphs such as connectivity and size of the maximum matching.
Nutan Limaye received her Ph.D. in Theoretical Computer Science from Institute of Mathematical Sciences, Chennai in 2009. She was a visiting fellow at Tata Institute of Fundamental Research (TIFR) from 2009 to 2010. She has been an assistant professor in the CSE department at IIT Bombay since 2010. Her primary research interests lie in complexity theory and algorithms. Her recent research has been on arithmetic circuit lower bounds, design of small depth proof systems and design of space efficient algorithms.