DIMACS Workshop on Discrete Metric Spaces and their Algorithmic Applications

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.