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

几何已经成为算法设计中的核心概念，在生物信息学和图划分等领域都是如此。这项研究是对基本数学问题的一大子集的一致和统一的攻击，这些问题通常与有限度量空间的几何嵌入有关。具体应用范围从聚类和学习到数据的紧凑表示到图划分到最近邻搜索。由于研究跨越了不同的领域，组建的团队是多学科的，包括分析师(Johnson和Naor)、几何学家(Gromov)、离散数学家和组合学家(Linial)和算法设计师(Arora和Charikar)。正在进行的算法几何化产生的研究领域是数学和计算机科学的一个令人兴奋的新前沿。例如，像Lipschitz延拓这样的深层数学结果可能被证明应用于简洁地表示计算机声音的实际问题。反过来，算法设置为数学理论提供了肥沃的新土壤。研究人员研究数据的几何表示和到结构化空间的低失真映射。研究了在NP-Hard问题的近似算法设计中出现的度量，特别是了解它们的局部和全局性质。这项研究对实际中重要的度量有了新的理解，如推土机和编辑距离度量，这些度量是根据计算工作量定义的，因此在数学上还没有研究过。

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.