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

几何已经成为算法设计的核心概念，在生物信息学和图划分等不同领域都是如此。这项研究是一个协调和统一的攻击，对潜在的数学问题的一个大子集，这往往与有限度量空间的几何嵌入有关。具体的应用范围从聚类和学习到数据的压缩表示，再到图划分和最近邻搜索。由于研究跨越了多个领域，因此组建的团队是多学科的，包括分析师（Johnson和Naor）、几何学家（Gromov）、离散数学家和组合学家（Linial）以及算法设计师（Arora和Charikar）。正在进行的算法几何化的研究领域是数学和计算机科学的一个令人兴奋的新前沿。例如，深奥的数学结果，如利普希茨扩展，最终可能会应用于紧凑地表示计算机声音的实际问题。反过来，算法设置为数学理论提供了肥沃的新土壤。研究人员研究数据的几何表示和低畸变映射到结构化空间。研究了np困难问题的近似算法设计中出现的度量，特别是为了了解它们的局部与全局性质。该研究为实际重要的度量（如土方和编辑距离测量）提供了新的理解，这些度量是根据计算努力定义的，因此没有在数学中进行研究。

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.