This Career Development Plan is focused on Metric Embeddings, a powerful area of algorithms research. Interest in embeddings stems from their broad algorithmic applicability; they are being used extensively to obtain solutions and design algorithms that are simple, elegant and versatile. The use of metric embeddings has often allowed ad-hoc methods to be replaced by powerful general principles, and has suggested new approaches to tackle long-standing open problems. The impact of these techniques can be seen on problems in finding graph separators, data clustering, network design, streaming computation, and geometric and on-line algorithms, to name but a few.
This research intends to focus on the algorithmic theory of embeddings in the context of these applications. Informally, an embedding is a map of an arbitrary metric space into a ``simpler'' one which does not alter distances by much, and the focus of this research is on two natural and fundamental themes: (a) to investigate the complexity of metric spaces from an algorithmic perspective, and to use this to develop efficient algorithms, and (b) to develop embeddings that simplify metrics; i.e. embed general metric spaces to well-understood simpler ones.
This proposal offers a broad spectrum of research opportunities at both graduate and undergraduate levels: these include the investigation of theoretical principles, the development of algorithms and embeddings, and the implementation and experimental evaluation of these results. Progress in this research will influence the curriculum via special courses presenting theoretical advances along with their applications. Workshops and seminars will be used to promote interdisciplinary research.
