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.