AF: Small: Metric Geometry for Combinatorial Problems

AF：小：组合问题的度量几何

• 批准号: 1217256
• 负责人: James Lee
• 金额: $ 40万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217256&HistoricalAwards=false
• 关键词: AF; Small; Metric; Geometry; Combinatorial

Geometric spaces arise in computer science through a number of avenues. The most obvious of these occurs when the input data for a problem possesses an inherent metric structure, like the hop-distance between nodes in a network, or the similarity distance between pairs of genomic sequences. But there are other, more subtle examples, like the geometry of sparse vectors, which arises prominently in coding theory, signal recovery, and quantum information, or the effective resistance distance between nodes in an electrical network, which has proven to be a powerful algorithmic tool in attacking both algebraic and combinatorial problems.Perhaps most strikingly, in the setting of combinatorial optimization, high-dimensional geometry often presents itself in an unexpected and profound manner. A basic example is the use of convex optimization in the solution---exact or approximate---to a variety of combinatorial problems. In many cases, a problem with an a priori purely combinatorial structure is shown to involve rich geometric phenomenon. Furthermore, we now realize that often this structure is inherent and fundamental, in the sense that any solution to the problem must confront its geometric core.The PI will seek to understand these connections and develop new algorithmic techniques to exploit them. This work will employ techniques from high-dimensional geometry and probability, functional analysis, spectral geometry, and combinatorics to attack problems at the forefront of computer science. This includes addressing fundamental gaps in our understanding of theoretical issues, as well as developing solutions to practical problems that arise from the need to analyze and manipulate massive data sets. To achieve these goals, the investigator intends to address central, important open problems in the fields of approximation algorithms, high-dimensional information theory, and discrete asymptotic convex geometry.

几何空间通过多种途径出现在计算机科学中。 其中最明显的情况发生在问题的输入数据具有固有的度量结构时，例如网络中节点之间的跳跃距离，或基因组序列对之间的相似性距离。 但还有其他更微妙的例子，比如稀疏向量的几何形状，它在编码理论、信号恢复和量子信息中突出出现，或者电网中节点之间的有效电阻距离，它已被证明是一种强大的算法解决代数和组合问题的工具。也许最引人注目的是，在组合优化的背景下，高维几何常常以意想不到的深刻方式呈现。 一个基本的例子是在解决各种组合问题时使用凸优化（精确或近似）。 在许多情况下，具有先验纯组合结构的问题被证明涉及丰富的几何现象。 此外，我们现在意识到，这种结构通常是固有的和基本的，任何问题的解决方案都必须面对其几何核心。PI 将寻求理解这些联系并开发新的算法技术来利用它们。 这项工作将采用高维几何和概率、泛函分析、谱几何和组合学等技术来解决计算机科学前沿的问题。 这包括解决我们对理论问题理解的根本差距，以及为因分析和操作海量数据集的需要而出现的实际问题制定解决方案。 为了实现这些目标，研究人员打算解决近似算法、高维信息论和离散渐近凸几何领域中的核心、重要的开放问题。