SODA accepts...

As noted here, here, and here, the SODA accepts have been announced. There are numerous cool looking papers. Particularly relevant to this blog are:

• On the Exact Space Complexity of Sketching and Streaming Small Norms [Kane, Nelson, Woodruff]
• Streaming Algorithms for extent problems in high dimensions [Agarwal, Sharathkumar]
• Efficiently Decodable Non-adaptive Group Testing [Indyk, Ngo, Rudra]
• Coresets and Sketches for High Dimensional Subspace Approximation Problems [Feldman, Monemizadeh, Sohler, Woodruff]
• 1-pass Relative-Error L_p-Sampling with Applications [Monemizadeh, Woodruff]
• Lower Bounds for Sparse Recovery [Do Ba, Indyk, Price]
• A Model of Computation for MapReduce [Karloff, Suri, Vassilvitskii]

(If you spot a version of any of the above papers online, please send me a link so I can add it. Cheers.)

UPDATE: Abstracts have now been posted. Also, the Geomblog has a “behind the scenes” look at the workings of this year’s SODA committee.