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
Tue Jul 22 12:38:43 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. A preliminary list of invited speakers and
participants is attached below.

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)

Preliminary list of invited speakers and participants:

  Dimitris Achlioptas, Microsoft
  Mihai Badoiu, MIT
  Yair Bartal, Hebrew University
  Bo Brinkman, Princeton University
  Jeremy Buhler, Washington University
  Bernard Chazelle, Princeton University
  Chandra Chekuri, Bell Labs
  Victor Chepoi, Universite de la Mediterranee, Marseille
  Graham Cormode, DIMACS
  Michel Deza, Ecole Normale Superieure
  Kedar Dhamdhere, CMU
  Michael Elkin, IAS Princeton
  Martin Farach-Colton, Rutgers University
  Sudipto Guha, University of Pennsylvania
  Anupam Gupta, CMU
  Bill Johnson, Texas A&M
  Nigel Kalton, University of Missouri
  Ravi Kumar, IBM Almaden
  Robert Krauthgamer, University of California, Berkeley
  James R. Lee, University of California, Berkeley
  Joram Lindenstrauss, Hebrew University
  Avner Magen, University of Toronto
  S. Muthukrishnan, Rutgers University
  Assaf Naor, Microsoft
  Seffi Naor, Technion
  Ilan Newman, Haifa University
  Yuval Rabani, Technion
  R. Ravi, CMU
  Amit Sahai, Princeton University
  Cenk Sahinalp, CWRU
  Stephen Semmes, Rice University
  Martin Strauss, AT&T Labs
  Kunal Talwar, University of California, Berkeley
  Santosh Vempala MIT
  Avi Wigderson, IAS Princeton
  David Woodruff, MIT

Workshop Program:
This is a preliminary program.

Wednesday, August 20, 2003

 8:30 -  9:00  Breakfast and registration

 9:00 -  9:30  Introduction
               Jiri Matousek
 9:30 - 11:00  Tutorial: Embeddings and approximation algorithms for NP-hard problems
               Ramamoorthi Ravi

11:15 - 12:00  Approximating arbitrary metrics by tree metrics
               Kunal Talwar

12:00 -  1:30  Lunch

 1:30 -  2:15  Approximating minimum average distortion of non-contracting embeddings
               Kedar Dhamdhere

 2:15 -  3:00  Approximation Algorithms for Embedding Metrics into Two-dimensional Space
               Mihai Badoiu

 3:30 -  4:15  Approximating steiner k-cuts
               Chandra Chekuri

 4:15 -  5:00  Average distortion
               Yuri Rabinovich

Thursday, August 21, 2003 

 9:00 -  9:30  Breakfast and registration

 9:30 - 11:00  Tutorial: Lipschitz quotient maps between Banach spaces
               Bill Johnson

11:15 - 12:15  The analogies between the structure theory of finite metric spaces and 
               the local theory of Banach spaces- past, present and future
               Assaf Naor

12:15 -  1:30  Lunch

 1:30 -  2:15  Preduals of spaces of Lipschitz functions and
               applications to Lipschitz structure
               Nigel Kalton

 2:15 -  3:00  TBA
               Stephen Semmes

 3:30 -  4:15  A unified approach to Lipschitz extension
               James R. Lee 

 4:15 -  5:15  Graph classes defined by distance properties
               Victor Chepoi

Friday, August 22, 2003

 9:00 -  9:30  Breakfast and registration

 9:30 - 10:15  Impossibility of dimension reduction in l_1
               Bo Brinkman 

10:15 - 10:35  The impossibility of dimension reduction in L_1
               Assaf Naor

10:50 - 11:35  The intrinsic dimensionality of graphs
               Robert Krauthgamer 
11:35 - 12:20  Bounded geometries, fractals and low distortion embeddings
               Anupam Gupta

12:20 -  2:00  Lunch

 2:00 -  2:45  Ramsey-type metric phenomena
               Yair Bartal

 2:45 -  3:30  TBA
               Manor Mendel 

 4:00 -  4:45  Embedding box metrics in l_p
               Avner Magen

 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
11:15 - 12:00  TBA
               Graham Cormode

12:00 -  1:30  Lunch

 1:30 -  2:15  Similarity estimation, rounding algorithms and metric embeddings
               Moses Charikar

 2:15 -  3:00  Stream-based geometric algorithms
               Piotr Indyk

 3:00 -  3:45  Embeddings of distances derived from DNA and
               protein similarity scoring matrices
               Jeremy Buhler

 4:15 -  5:00  Tight Lower Bounds for the Distinct Elements Problem
               David Woodruff

 5:00 -  5:45  On the hardness of approximate proximity search for
               non-metric/non-geometric spaces
               Cenk Sahinalp


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