AF: Small: Metric Geometry for Combinatorial Problems

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

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.