- Optimal Sampling From Distributed Streams [Cormode, Yi, Zhang, Muthukrishnan]
- Fast Manhattan Sketches in Data Streams [Nelson, Woodruff]
- An Optimal Algorithm for the Distinct Elements Problem [Kane, Nelson, Woodruff]
I also like the look of the PODS tutorial on “Information Complexity” that will be presented by T. S. Jayram. This is one of the most important techniques for proving stream and communication lower bounds. Check out the abstract here.
UPDATE: “An Optimal Algorithm for the Distinct Elements Problem” received the PODS Best Paper Award. Congrats!
[FWIW, I also had a paper accepted but it was on differential privacy rather than data streams. Perhaps I should add "secrecy" as a semi-suitable synonym to subjoin to the blog's "streams, sketches, samples, sensing" tagline. Or would that be silly?]