Show icon Show search tips...
Hide icon Hide search tips...

[Sy-cg-global] [Publicity-list] DIMACS Workshop on Discrete Metric Spaces and their Algorithmic Applications

Linda Casals lindac at
Wed Aug 13 11:58:47 EDT 2003

 DIMACS Workshop on Discrete Metric Spaces
	and their Algorithmic Applications 
August 20 - 23, 2003 
Princeton University, Princeton, New Jersey


 Moses Charikar	   Princeton University	moses at CS.Princeton.EDU  
 Piotr Indyk	   MIT			indyk at  
 Nati Linial	   Hebrew University	nati at  
 Jiri Matousek	   Charles University	matousek at  
 Yuri Rabinovich   University of Haifa	yuri at  
 Gideon Schechtman Weizmann Institute	gideon at

Co-sponsored by the Institute for Advanced Study and Princeton University.

Presented under the auspices of the DIMACS Special Focus on Data
   Analysis and Mining 


The study of finite metric spaces and metric embeddings has its
origins in Banach space theory and functional analysis. In recent
years, this area has emerged as a new and influentual branch of
discrete mathematics, with deep and surprising applications in
Computer Science. Theoretical computer scientists are now familiar
with the work of Bourgain, who showed that any metric on n points can
be embedded with O(log n) distortion in Euclidean space, as well as
the fundamental dimension reduction result of Johnson and
Lindenstrauss who showed that any n points in Euclidean space can be
embedded in O(log(n)/ e 2 ) dimensions with a (1 + e )-distortion in
distances. Following the work of Linial, London and Rabinovich,
Bourgain's result has found novel applications to approximation
algorithms. The Johnson Lindenstrauss lemma has been used as a basic
tool for dealing with high dimensional data. It has also been used
extensively in the design of algorithms and data structures for
various problems in high dimensional computational geometry.

There has been a lot of interest and activity in this area in the past
few years. New insights into metric embeddings have been developed as
well as new applications and connections discovered to approximation
algorithms, algorithms for large data sets, and algorithms for high
dimensional computational geometry. In the last two years, there have
been several surveys on the subject. Piotr Indyk gave a tutorial at
FOCS 2001 on algorithmic applications of low distortion
embeddings. Jiri Matousek wrote a chapter on mathematical aspects of
embeddings in his recent book on discrete geometry. Nati Linial gave a
survey on finite metric spaces and their connec-tion to combinatorics,
geometry and algorithms at the International Congress of
Mathematicians last year. Also, Piotr Indyk and Jiri Matousek recently
wrote a chapter on low distortion embeddings of finite metric spaces
for the upcoming Handbook of Discrete and Computational Geometry.

Last year, a workshop on discrete metric spaces was held at Haifa,
March 3-7, 2002 and was quite successful
( Besides bringing together
researchers in the area and facilitating research and discussion, one
of the achievements of the workshop was to compile a list of open
problems in the field,
( The large list of
intriguing open problems is a good indication of the vitality of this
area. Also interesting to note is the fact that since that list was
compiled, 5 open questions on that list have been resolved (as of Jan
27, 2003).

Given the furious pace of new developments in this area, we plan to
organize a followup work-shop in Princeton this summer. In particular,
we would like to take advantage of the following opportunity: the
RANDOM and APPROX conferences will be held in Princeton Aug 24-26,
2003. We intend to have our workshop just before the conference and
take advantage of the fact that there is a significant overlap between
the target audience of the workshop and that of RANDOM-APPROX. Also,
we expect that several interested US participants who could not take
advantage of the Haifa workshop last year will find it easier to
attend the workshop in Princeton.

The questions in this field are a beautiful blend of combinatorics and
geometry with several con-nections to algorithm design and
analysis. Here are some of the topics that the proposed workshop will

    * Embeddings in normed spaces and connections to Banach space theory.
    * Embeddings of planar graphs, low distortion embeddings into
           trees and their applications to approximation algorithms.
    * Metric Ramsey type theorems.
    * Low dimensional embeddings and connections to algorithmic
           techniques for large data sets.
    * Embeddings of special metrics (e.g. edit distance, frechet
        distance, etc.) and applications to high dimensional
        computational geometry.
    * Graph representations, distance labelings, graph spanners, etc. 


Call for Participation:

The workshop will consist of invited presentations of researchers
working in the field of embeddings and related areas of mathematics
and computer science. 

In addition, the workshop will feature several tutorials on embeddings
as well as their algorithmic applications. A partial list of tutorials

 * - "Embeddings and computation over streaming data" (S. Muthukrishnan)
 * - "Embeddings and approximation algorithms for NP-hard problems" (R. Ravi)
 * - "Lipschitz quotient maps between Banach spaces" (Bill Johnson)


Workshop Program:

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
               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  TBA
               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  Average distortion
               Yuri Rabinovich, University of Haifa

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

Registration Fees:

(Pre-registration deadline: August 13, 2003)***********

Regular rate
Preregister before deadline $120/day
After preregistration deadline $140/day

Reduced Rate*
Preregister before deadline $60/day
After preregistration deadline $70/day

Preregister before deadline $10/day
After preregistration deadline $15/day

DIMACS Postdocs $0

Non-Local Graduate & Undergraduate students
Preregister before deadline $5/day
After preregistration deadline $10/day

Local Graduate & Undergraduate students $0
(Rutgers & Princeton)

DIMACS partner institution employees** $0

DIMACS long-term visitors*** $0

Registration fee to be collected on site, cash or check only.

Our funding agencies require that we charge a registration fee for the
workshop. Registration fees cover participation in the workshop, all
workshop materials, breakfast, lunch, breaks, and any scheduled social
events (if applicable).

* College/University faculty and employees of non-profit organizations
will automatically receive the reduced rate. Other participants may
apply for a reduction of fees. They should email their request for the
reduced fee to the Workshop Coordinator at
workshop at  Include your name, the Institution you
work for, your job title and a brief explanation of your
situation. All requests for reduced rates must be received before the
preregistration deadline. You will promptly be notified as to the
decision about it.

** Fees for employees of DIMACS partner institutions are waived.
DIMACS partner institutions are: Rutgers University, Princeton
University, AT&T Labs - Research, Bell Labs, NEC Laboratories America
and Telcordia Technologies. Fees for employees of DIMACS affiliate
members Avaya Labs, IBM Research and Microsoft Research are also

***DIMACS long-term visitors who are in residence at DIMACS for two or
more weeks inclusive of dates of workshop.


Information on participation, registration, accommodations, and travel
can be found at:


More information about the Dimacs-sy-cg-global mailing list