Data Streams in Barbados

Denis Therien (humor that you can hear rustle even over emails!) has long organized the Annual Workshop on Computational Complexity at Barbados. This year I will give lectures on Data Streams. This is not like giving a talk to the general algorithmic audience where you inspire and show some technical gems, or like giving a summer course to the graduate students where you develop the material methodically so the structure falls into place and exercises follow. I need to get into detailed proofs and leave the audience of seasoned researchers at the cusp of difficult, important open problems. Here is my tentative plan.

Basic data stream models & motivations Sketches for forward distribution problems (quantiles, heavy hitters, geometric problems, linear algebraic problems) Distinct sampling for inverse distribution problems (distinct elements, rarity, graph matching) Lower bounds (frequency moments, general graph properties) Other models (continuous communication complexity, probabilistic streams, MapReduce, multipass) Connection to other areas (sparse approximation and compressed sensing, embeddings, machine learning)

Now comes the call: please send me comments, criticisms, suggestions, and slides of your results if you are willing, so I can piece together the best coverage of material in this area.