Presented under the auspices of the DIMACS Special Focus on Data Analysis and Mining
Wednesday, August 20, 2003
8:30 - 9:00 Breakfast and registration
9:00 - 9:30 Introduction
Jiri Matousek, Charles University
9:30 - 11:00 Tutorial: Embeddings and approximation algorithms for NP-hard problems
Ramamoorthi Ravi, Carnegie Mellon University
11:00 - 11:15 Break
11:15 - 12:00 Approximating arbitrary metrics by tree metrics
Kunal Talwar, University of California, Berkeley
12:00 - 1:30 Lunch
1:30 - 2:15 (Nearly) Optimal Embeddings into Additive and Ultrametric Trees
Martin Farach-Colton, Rutgers University
2:15 - 3:00 Approximating minimum average distortion of non-contracting embeddings
Kedar Dhamdhere, Carnegie Mellon University
3:00 - 3:30 Break
3:30 - 4:15 Approximation Algorithms for Embedding Metrics into Two-dimensional Space
Mihai Badoiu, MIT
4:15 - 5:00 Generic Global Rigidity
Bob Connelly, Cornell University
5:00 - 5:15 Break
5:15 - 6:00 Approximating steiner k-cuts
Chandra Chekuri, Bell Laboratories
Thursday, August 21, 2003
9:00 - 9:30 Breakfast and registration
9:30 - 11:00 Tutorial: Lipschitz quotient maps between Banach spaces
Lipschitz quotient (slides)
Bill Johnson, University of Texas, A&M
11:00 - 11:15 Break
11:15 - 12:00 The analogies between the structure theory of finite metric spaces and
the local theory of Banach spaces- past, present and future
Assaf Naor, Microsoft Research
12:00 - 1:00 Lunch
1:00 - 1:45 Preduals of spaces of Lipschitz functions and
applications to Lipschitz structure
Nigel Kalton, University of Missouri
1:45 - 2:30 Metric Spaces 1
Metric Spaces 2
Stephen Semmes, Rice University
2:30 - 3:00 Break
3:00 - 3:45 A unified approach to Lipschitz extension
James R. Lee, University of California, Berkeley
3:45 - 4:30 On Sobolev spaces on finite graphs
Mikhail Ostrovskii
4:30 - 4:45 Break
4:45 - 5:30 Graph classes defined by distance properties
Victor Chepoi, Universite' de la Mediterrane'e, Marseille
5:30 - 6:15 Embedding treewidth-2 graphs into l_1 revisited
Yuri Rabinovich, University of Haifa
6:30 - 7:30 Reception
Friday, August 22, 2003
9:00 - 9:30 Breakfast and registration
9:30 - 10:15 Impossibility of dimension reduction in l_1
Bo Brinkman, Princeton University
10:15 - 10:35 The impossibility of dimension reduction in L_1
Assaf Naor, Microsoft Research
10:35 - 10:50 Break
10:50 - 11:35 The intrinsic dimensionality of graphs
Robert Krauthgamer, IBM Almaden
11:35 - 12:20 Bounded geometries, fractals and low distortion embeddings
Anupam Gupta, Carnegie Mellon University
12:20 - 2:00 Lunch
2:00 - 2:45 On metric Ramsey-type Phenomena
Manor Mendel, Hebrew University
2:45 - 3:30 Ramsey Theorem for Metric Spaces+
Yair Bartal, Hebrew University
4:00 - 4:45 Embedding box metrics in l_p
Avner Magen, University of Toronto
5:00 - ... Rump session (open problems and short communications)
<= 5 minutes per speaker
Saturday, August 23, 2003
9:00 - 9:30 Breakfast and registration
9:30 - 11:00 Tutorial: Embeddings and computation over streaming data
S. Muthu Muthukrishnan, Rutgers University
11:00 - 11:15 Break
11:15 - 12:00 Zeroing in on the L0 metric
Graham Cormode, Rutgers University
12:00 - 1:30 Lunch
1:30 - 1:55 Similarity estimation, rounding algorithms and metric embeddings
Moses Charikar, Princeton University
1:55 - 2:20 Experiments with Embedding Earth-Mover Distance into Normed Spaces
Piotr Indyk, MIT
2:20 - 2:45 Experiments with Random Projections for Machine Learning
Dmitriy Fradkin, Rutgers University
2:45 - 3:30 Exploiting embeddings of Biosequence Similarity Scores
Jeremy Buhler, Washington University in St. Louis
3:30 - 4:00 Break
4:00 - 4:45 Lower bounds for L_infty approximations in data streams
Ravi Kumar, IBM Almaden
4:45 - 5:10 Tight Lower Bounds for the Distinct Elements Problem
David Woodruff, MIT
5:10 - 5:55 On the hardness of approximate proximity search for
non-metric/non-geometric spaces
Cenk Sahinalp, Case Western Reserve University
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage