Papers accepted for STOC include:
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance [Chakrabarti, Regev]
- Near-Optimal Private Approximation Protocols via a Black-Box Transformation [Woodruff]
- Fast Moment Estimation in Data Streams in Optimal Space [Kane, Nelson, Porat, Woodruff]
- Privacy-preserving Statistical Estimation with Optimal Convergence Rates [Smith]
- Subspace Embeddings for the L_1-norm with Applications [Sohler, Woodruff]
- A Unified Framework for Approximating and Clustering Data [Feldman, Langberg]
2 comments
Comments feed for this article
February 8, 2011 at 5:39 pm
Anonymous
Are you able to provide an opinion on the Chakrabarti-Regev result? From an outsider’s perspective, it seems to be a pretty big and useful result.
February 20, 2011 at 8:29 pm
Andrew
Yes, it’s definitely a good result. The previous bound in RANDOM 2010 is also worth checking out — the result is weaker but the technique is v. nice. I’ll see about having a post about the result soon (famous last words!)