Collaborative Research: MSPA-MCS: Embeddings of Finite Metric Spaces - A Geometric Approach to Efficient Algorithms

点击翻译按钮获取中文摘要

Geometry has become a central notion in algorithm design, in fieldsas diverse as bioinformatics and graph partitioning.This research is a concerted and unified attack on a large subset of theunderlying mathematical problems, which often have to do withgeometric embeddings of finite metric spaces.The concrete applications range from clustering and learning tocompact representation of data to graph partitioning tonearest neighbor searching. Since the research spans aa variety of fields, the assembled team is multidisciplinary,involving analysts (Johnson and Naor), a geometer (Gromov),a discrete mathematician and combinatorialist (Linial)and algorithm designers (Arora and Charikar).The research area emerging from the ongoing geometrization ofalgorithms is an exciting new frontier for both mathematics andcomputer science. For example, deep mathematical results such asLipschitz extension may turn out to have applicationsto the practical problem of compactly representing computer sounds.In turn, algorithmic settings provide a fertile new ground formathematical theory. The investigators study geometric representationsfor data and low disortion mappings into structured spaces. Metrics thatarise in the design of approximation algorithms for NP-hard problems arestudied, especially to understand their local versus global properties.The research develops new understanding for practicallyimportant metrics such as earth mover and edit distancemetrics, which are defined in terms of computational effort and havethus not been studied in mathematics.