Hide search tips...
- The wildcard * means "match zero or more characters" and may only be used at the end of a word.
- The wildcard ? means "match exactly one character" and cannot be used as the first character of a word.
- To search for a phrase in a document, use double-quotes to delimit your search terms -- for example, "search phrase".
- Find out more information about searching.
[Sy-cg-global] [Publicity-list] DIMACS Workshop on Discrete Metric Spaces and their Algorithmic Applications
Linda Casals
lindac at dimacs.rutgers.edu
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
ORGANIZERS
Moses Charikar Princeton University moses at CS.Princeton.EDU
Piotr Indyk MIT indyk at theory.lcs.mit.edu
Nati Linial Hebrew University nati at cs.huji.ac.il
Jiri Matousek Charles University matousek at kam.mff.cuni.cz
Yuri Rabinovich University of Haifa yuri at cs.haifa.ac.il
Gideon Schechtman Weizmann Institute gideon at wisdom.weizmann.ac.il
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
(http://cs.haifa.ac.il/~yuri/DMSA02.html). 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,
(http://kam.mff.cuni.cz/~matousek/haifaop.ps). 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
cover:
* 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
includes:
* - "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
Postdocs
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 dimacs.rutgers.edu. 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
waived.
***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:
http://dimacs.rutgers.edu/Workshops/MetricSpaces/
**PLEASE BE SURE TO PRE-REGISTER EARLY**
*********************************************************
More information about the Dimacs-sy-cg-global
mailing list
Show search tips...