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]
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.
- Lower bounds in Communication Complexity by Lee and Shraibman
- Information Complexity: A Tutorial by Jayram
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!)
Recent Comments