The 16th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 29th to March 7th, 2004. Participants are expected to arrive on Sunday afternoon, February 29th. The topic of this year's workshop will be "Finite metric spaces and low dimensional embeddings".
Main Speaker: Nati Linial, Hebrew University of Jerusalem
Guest Speaker: Santosh Vempala, MIT
Nati LinialTitle:
School of Computer Science and Engineering
The Hebrew University of Jerusalem
Jerusalem 91904
Israel
email: nati@huji.ac.il
phone: +972-2-6585237
Abstract:"Finite metric spaces and what they are good for"
Interest in finite metric spaces has grown tremendously over the last years. A very fruitful leitmotiv of modern discrete mathematics is the geometrization of combinatorics: This is the idea that one gains a lot by observing discrete objects (e.g. graphs) from a geometric perspective. The theory of finite metric spaces is one of the clearest manifestations of this general principle.
There are many important problems in the modern theory of algorithms where metric spaces are part of the problem definition: For example, questions such as the search for a nearest neighbor in given point set. Many of these problems can be viewed as high-dimensional analogues of questions ususally considered in 2 or 3 dimensions in computational geometry. There are also many examples that come from online computation. It turns out, however, that the theory of finite metric spaces can be used with great success in the design of approximation algorithms for numerous hard problems whose formulation does not involve any metric.
At present, the most highly developed parts of the theory concern low-distortion embeddings into normed spaces. Given a finite metric space, we want to map it into some normed space so that distances among points are maintained as well as possible. It is not too surprising that at this point the theory gets strongly influenced by the highly developed theory of finite dimensional normed spaces.
There are several pleasant features to this area: A large number of beautiful results and unexpected applications. It is also rich in open problems, and progress in their resolution in recent years has been spectacular.In this series of talks I will cover some of the known theory and applications and discuss some of the directions for future research.
Santosh VempalaTitle:
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA, USA 02139
email: vempala@math.mit.edu
phone: (617) 253-4064
"Algorithmic Applications of Embeddings"Abstract:
These lectures, designed to complement Nati's, will cover the algorithmic applications of low-dimensional embeddings. We will tackle problems from combinatorial optimization (graph coloring, minimum bandwidth), machine learning and information retrieval (nearest neighbors, clustering), using the simple technique of random projection and developing interesting extensions to the basic theory of Euclidean embeddings.