Space-efficient algorithms for data streams

Vladimir Braverman, UCLA

Streaming algorithms is an important area of theoretical computer science with many practical applications. We will define the basic model of data streams and will explain some fundamental algorithms and methods that have shaped the area of data streams. Also, we will survey some of our recent results and discuss current challenges and open problems. In particular, we will present the paper “Zero-One Frequency Laws” (STOC 2010) where we investigate frequency-based functions and answer the main open question of Alon, Matias and Szegedi (STOC 1996).

Speaker Biography

Vladimir Braverman is a Ph.D. candidate at UCLA; his advisor is Rafail Ostrovsky. His main interests are algorithms for data streams, communication complexity and related areas. He received his B.Sc. and M.Sc. degrees from Ben-Gurion University Israel, where his advisor was Daniel Berend. Prior to attending UCLA, he led a research team at HyperRoll, working with Yossi Matias.