SODA09
From ResearchWiki
Contents |
Clustering
- Bodo Manthey and Heiko Roeglin, Improved Smoothed Analysis of the k-Means Method
- Maria-Florina Balcan, Avrim Blum and Anupam Gupta. Approximate Clustering without the Approximation
- S. Charles Brubaker. Clustering on Noisy Mixtures
- Marcel R. Ackermann and Johannes Blömer. Coresets and Approximate Clustering for Bregman Divergences*
Streaming
- Ping Li. Compressed Counting
- Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream
Embeddings
- Alexandr Andoni, Piotr Indyk and Robi Krauthgamer. Overcoming the L_1 Non-Embeddability Barrier: Algorithms for Product Metrics*
- Ittai Abraham, Yair Bartal and Ofer Neiman. On Low Dimensional Local Embeddings*
- William Johnson and Assaf Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite*
Misc
- Alexander Golynski. Lower Bounds for Succinct Data Structures*
- Yury Lifshits and Shengyu Zhang. Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.*
- Paolo Ferragina, Igor Nitto and Rossano Venturini. On the bit-complexity of Lempel-Ziv compression
- Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching
- Aurore Amaudruz and Christina Fragouli. Combinatorial Algorithms for Wireless Information Flow
- Justin Salez and Devavrat Shah. Optimality of Belief Propagation for Random Assignment Problem
