Monday, January 19, 2009

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.

Labels:

2 Comments:

Anonymous Anonymous said...

When are you planning to hold the workshop?

7:57 AM  
Anonymous aravind said...

Hi Metoo,

I haven't worked yet in this area, so I regret I am unable to help. However, I am looking forward to your slides (and stories) from Barbados, which I will be sure to point my Spring '09 class to.

7:05 AM  

Post a Comment

<< Home