Data Stream Algorithms

Lecturer: Prof. Piotr Indyk (MIT, USA).

About the lecturer | Course Summary | Slides | Assignment

About the lecturer: Piotr Indyk is a Professor of Electrical Engineering and Computer Science at MIT. He joined MIT in 2000, after earning a PhD from Stanford University. Earlier, he received Magister degree from Uniwersytet Warszawski in 1995. His research interests include high-dimensional computational geometry, sketching and streaming algorithms, sparse recovery and compressive sensing. He received the NSF CAREER Award, Sloan Fellowship and Packard Fellowship. He is an Associate Editor for the IEEE Transactions on Signal Processing.

Course summary: Data stream algorithms perform computation over a continuous streams of data using only a limited amount of memory. Such algorithms are of key importance in many applications, including analysis of massive data sets and network monitoring. The area has experienced a significant growth over the last decade. At the same time, the field has been enriched by the discovery of strong connections to other topics, such as randomized dimensionality reduction, metric embeddings, communication complexity and compressed sensing.

The goal of this course is to provide an in-depth introduction to some of the key issues in data stream computing, with the emphasis on theoretical tools for designing and analyzing efficient data stream algorithms. Specific topics include:

Slides:

Assignment: Tasks are here (sorted from the easiest to the hardest): [PDF]. Warning! -- a slight change in Problem 1!!!
Due: 8th January 2012. Please send a pdf to Lukasz Kowalik (kowalik malpa mimuw edu pl). Solutions should be prepared in LaTeX.