You are currently browsing the monthly archive for September 2010.

The list of accepted papers for SODA has been posted. Stream papers include:

If your paper ended up on the list of excepted papers, remember that the STACS deadline is this Friday. And there’s always STOC.

At some point the bite-sized series will get to communication complexity and its applications to proving data stream lower bounds. However, at the current rate of posting this will be some time in early 2016 (just as well proofs don’t expire). In case you don’t have that much patience, I wanted to mention two recent surveys/tutorials I just came across.

Or you could get started by reading Mihai’s posts from last year (1a, 1b, 2, 3, 4) or the draft chapter from Arora-Barak. Just don’t read them all at once.

Update. See also the slides from the “Communication and Information in Complexity” day at the recent Barriers 2 workshop. (Thanks Paul!)

If you’re interested, here and here are some freshly-minted slides for an easy 3 hour intro to data stream algorithms. Any comments/corrections welcome via email (especially if I receive them in the next few of hours!)


A research blog about data streams and related topics.

Recently Tweeted