You are currently browsing the monthly archive for February 2011.
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]