SODA09

From ResearchWiki

Contents 1 Clustering 2 Manifolds 3 Streaming 4 Embeddings and hi-D spaces 5 Information Retrieval 6 Misc

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*

Manifolds

• Siu-Wing Cheng and Man-Kwun Chiu. Dimension detection via slivers
• Misha Belkin, jian sun and Yusu Wang. Constructing Laplace operators from Point Clouds

Streaming

• Ping Li. Compressed Counting
• Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream
• Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup. Variance-optimal sampling-based estimation of subset sums

Embeddings and hi-D spaces

• 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
• Alexandr Andoni, Piotr Indyk, Robi Krauthgamer and Huy Nguyen. Approximate Nearest Neighbors for Affine Subspaces Queries

Information Retrieval

• Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh and Prabhakar Raghavan. Online story scheduling for web advertising

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
• Anthony Man-Cho So. Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints
• Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. Decomposition of Multiple Coverings into More Parts
• Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees. Here are some blog posts by Mihai on this work: I, II, III