The 21st McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from March 1st to March 8th, 2009. Participants are expected to arrive on Sunday afternoon, March 1st. The subject of this year's workshop will be data streams.
S. Muthu MuthukrishnanProposed outline
webpage
In order to deal with massive data that arrives rapidly and has to be processed instantly, the theoretical computer science community has developed the sublinear space, polylog time-per item, one-pass "data stream" model. In this course, we will study the theory of algorithms in the data stream model. Lectures will include:We start with the basic material from the book "Data Streams and Applications", but the advanced material is from the ongoing Stream 2.0 survey with Andrew McGregor.
- Data stream models and applications
- Forward distributions and Sketches
- Inverse distributions and Samples.
- Advanced Topic: Lower bounds in Data Stream model.
- Advanced Topic: Algorithms for graph, geometric, matrix streams.
- Advanced Topic: Second generation models including multipass, MapReduce and Probablistic streams.
- Applications beyond data streams: compressed sensing, machine learning.