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

几何已经成为算法设计的核心概念，在生物信息学和图划分等不同领域。这项研究是对一个大的基本数学问题子集的协调和统一的攻击，这些问题通常与有限度量空间的几何嵌入有关。具体应用范围从聚类和学习到数据的紧凑表示，再到图划分到最近邻搜索。由于这项研究跨越了多个领域，这个团队是多学科的，包括分析师（约翰逊和Naor）、几何学家（Gromov）、离散数学家和组合学家（Linial）以及算法设计师（Arora和Charikar）。例如，像Lipschitz扩展这样的深层次数学结果可能会应用于计算机声音的压缩表示的实际问题。反过来，算法设置为数学理论提供了一个肥沃的新土壤。研究人员研究数据的几何表示和低失真映射到结构化空间。研究了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.