CAREER: Geometric Techniques for Algorithm Design

该项目侧重于应用几何和解析技术从纯数学到算法理论的基本问题的研究。首席研究员的目标是开发两套数学工具及其在算法设计中的应用：积分几何和谱/微分图论。在前者中，他的目标是研究几何概念（如长度和体积）在构型空间中的应用，以理解组合算法的复杂性和多面体图的直径。在后者中，他建议努力理解在图上使用类似于连续微分几何和调和分析的结构的正确方法，如拉普拉斯算子、格林函数、霍奇结构和连接。首席研究员打算将这些技术应用于各种算法追求，包括：*寻找线性规划的强多项式时间算法；*新的非凸优化算法；*在无向图中寻找(1+epsilon)-近似最大流量的更快算法；*开发了一套通用工具，用于设计近线性时间图算法；以及分布式路由协议和其他分散的本地图算法。除了推进算法理论中几个核心问题的理论研究外，本研究还具有广泛实际影响的潜力。近年来，越来越多的情况是，世界上的许多地方都可以通过非常大的图形来有效地建模，无论它们是相互连接的计算机、社交网络还是道路集合。这些图通常非常大，即使是二次算法也会非常慢。因此，设计在近线性时间内运行的算法的有效工具变得越来越重要。此外，现在越来越多的人关注让松散协调的计算机集合一起工作来解决大型算法任务。在这两种情况下，谱/微分图理论的发展具有很大的前景。主要研究者打算发展的微分几何和类似离散理论旨在综合局部信息来推断全局性质。因此，谱和微分图理论为开发近线性时间算法和分布式时间算法提供了一种通用方法。此外，线性规划被应用于解决各种领域的大量实际问题，包括经济学、运筹学、组合优化和物流。对它的任何算法改进都会扩大这类问题的范围，这些问题可以实际解决。

This project focuses on the application of geometric and analytic techniques from pure mathematics to the study of fundamental questions in the theory of algorithms.The principal investigator aims to develop two sets of mathematical tools and their applications to algorithm design: integral geometry and spectral/differential graph theory. In the former, he aims to study the use of geometric concepts such as lengths and volumes in configuration spaces to understand the complexity of combinatorial algorithms and the diameters of polytope graphs. In the latter, he proposes to work on understanding the right way to employ structures on graphs analogous to those of continuous differential geometry and harmonic analysis, such Laplacians, Green's functions, Hodge structures, and connections.The principal investigator intends to apply these techniques to a variety of algorithmic pursuits, including:* the search for a strongly polynomial time algorithm for linear programming;* new algorithms for nonconvex optimization;* a faster algorithm for finding (1+epsilon)-approximate maximum flows in undirected graphs;* the development of a general set of tools for designing nearly linear time graph algorithms; and* distributed routing protocols and other decentralized and local graph algorithms.In addition to advancing the theoretical study of several central questions in the theory of algorithms, this research holds the potential for broad practical impact. In recent years, it has increasingly become the case that much of the world can be effectively modeled by very large graphs, whether they be interconnected computers, social networks, or collections of roads. These graphs are often so large that even a quadratic algorithm would be impractically slow. For this reason, effective tools for designing algorithms that run in nearly linear time are becoming more and more important. In addition, there is an increasing focus now on having collections of loosely coordinated computers work together to solve large algorithmic tasks. In both cases, the development of spectral/differential graph theory holds great promise. Differential geometry and the analogous discrete theory that the principal investigator intends to develop aim to synthesize pieces of local information to deduce global properties. As such, spectral and differential graph theory provide a general approach to developing both nearly-linear time algorithms and distributed ones. Furthermore, linear programming is applied to solve a vast array of practical problems in a wide variety of fields, inclding economics, operations research, combinatorial optimization, and logistics. Any algorithmic improvement for it would broaden the set of such problems that can be practically solved.