You are currently browsing the monthly archive for September 2010.
The list of accepted papers for SODA has been posted. Stream papers include:
- The Streaming Complexity of Cycle Counting, Sorting By Reversals, and Other Problems [Verbin, Yu]
- Efficient Sketches for the Set Query Problem [Price]
- Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Low Error [Jayram, Woodruff]
- Streaming k-means on Well-Clusterable Data [Braverman, Meyerson, Shindler, Ostrovsky, Roytman, Tagiku]
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.
- Lower bounds in Communication Complexity by Lee and Shraibman
- Information Complexity: A Tutorial by Jayram
Update. See also the slides from the “Communication and Information in Complexity” day at the recent Barriers 2 workshop. (Thanks Paul!)