CAREER: Geometric Techniques for Algorithm Design

点击翻译按钮获取中文摘要

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.