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将寻求理解这些连接并开发新的算法技术来利用它们。 这项工作将采用高维几何形状和概率，功能分析，光谱几何形状和组合学的技术来攻击计算机科学最前沿的问题。 这包括解决我们对理论问题的理解中的基本差距，以及为进行分析和操纵大规模数据集的需要而开发解决实践问题的解决方案。 为了实现这些目标，研究人员打算解决近似算法，高维信息理论和离散渐近凸几何的中心，重要的开放问题。