## 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:

- Estimating norms and other statistics of data streams
- Computing heavy hitters and compressed sensing
- Algorithms for metric and geometric data streams

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