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)/ ε 2 ) dimensions with a (1 + &epsilon )-
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 connection 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 workshop 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 connections to algorithm design and analysis. Here are some of the topics that the proposed workshop will cover:
Next: Call for Participation
Workshop Index
DIMACS Homepage