Tuesday, July 14

MS15
Randomized Algorithms

3:30 PM-6:00 PM
Room: Sidney Smith 2110

Randomization has proved to be a powerful tool in the design of efficient graph and network algorithms. The speakers in this minisymposium will highlight some of the recent advances in the area, including new and novel uses in geometric contexts.

3:30 Efficient Approximation Schemes for Euclidean TSP and Other Geometric Problems

Sanjeev Arora, Princeton University

4:00 Tornado Codes

Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman, and Volker Stemann, International Computer Science Institute

4:30 Approximation Algorithms Through Randomized Rounding

Aravind Srinivasan, National University of Singapore, Singapore

5:00 Nearest Neighbor Searching in Metric Spaces

Kenneth L. Clarkson, Bell Laboratories, Lucent Technologies

5:30 Randomized Nonlinear Projections Uncover High-Dimensional Structure

Lenore J. Cowen, Organizer