Dear Partners,

In the following website, you'll find SODA 2009 accepted papers and their abstracts.

http://www.cs.brown.edu/people/claire/SODAAccepts

If you are interested in theoretical computer science, it's a must that you take a look at it. Let me highlight a few that might fit in the main theme of our lab.

Uriel Feige and Noga Alon. On the power of two, three and four probes
David Eppstein and Elena Mumford. Self-overlapping Curves Revisited
Sudipto Guha, Kamesh Munagala and Peng Shi. Approximation Algorithms for Restless Bandit Problems
Vida Dujmovic, John Howat and Pat Morin. Biased Range Trees
Mikkel Thorup. String Hashing for Linear Probing
Christos Boutsidis, Michael Mahoney and Petros Drineas. An Improved Approximation Algorithm for the Column Subset Selection Problem
Joel Tropp. Efficient Algorithms for Column Subset Selection
(Column Subset Selection again!)
Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching
Bernard Chazelle. Natural Algorithms
Timothy M. Chan. Comparison-Based, Time-Space Lower Bounds for Selection
Ping Li. Compressed Counting
Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream
(Kuan-Yu should read this one.)
Michael Bender, Jeremy Fineman and Seth Gilbert. Online Topological Ordering
(Hsiao-Fei is one of the experts for this topic. Is O(n^2) achievable?)
Maria-Florina Balcan, Avrim Blum and Anupam Gupta. Approximate Clustering without the Approximation
Lorenz Minder and Alistair Sinclair. The extended k-tree algorithm

Von Voyage,

Kun-Mao