Design of Fast Algorithms using Continuous Methods

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

In this proposal, we aim to develop fast algorithms for several classic graph problems and numerical linear algebra problems using methods from continuous optimization and random matrix analysis. The use of tools from continuous optimization has been a major success story in the design of fast algorithms over the past few years. Combining tools such as near-linear time solvers for linear systems in Laplacian matrices from the seminal work of Spielman and Teng with methods from optimization such as gradient descent and interior point methods, has led to the development of the current fastest algorithms for classic combinatorial problems such as maximum flow, graph partitioning, bipartite matching, sampling random spanning trees etc.******Over the past year, my co-authors and I have built on tools from random matrix theory for better analyzing randomized processes on graphs, resulting in an algorithmic tool we refer to as randomized elimination [Kyng et al ‘16, Kyng-Sachdeva '16]. This has already led to a number of advances, including the simplest Laplacian solver [Kyng-Sachdeva '16], nearly-linear time solver for linear systems in block diagonally dominant (bDD) matrices [Kyng et al '16] (these systems arise when analyzing cryo-electron microscopy data), faster algorithms for sampling random spanning trees in graphs [Durfee et al '17a], and approximating determinants of Laplacians [Durfee et al '17b].******The key objective of this proposal is to develop these programs further and seek to design faster and improved algorithms for several fundamental problems. The first project under this proposal will be to develop randomized elimination based constructions for special trees. Specifically, we seek fast algorithms for low-stretch spanning trees, which are a fundamental component of several fast Laplacian solvers; and to incorporate random walk based ideas to design nearly-linear time algorithms for sampling random spanning trees.******The second project under this proposal will be to develop faster and simpler algorithms for several fundamental flow problems on graphs, including maximum-flow, bipartite matching, and multi-commodity flow. These are classic problems in theoretical computer science, where decades-old running time barriers have been broken with the help of continuous methods.******The third project under this proposal will be to build solvers for more classes of linear systems such as those arising from analyzing truss structures and RLC circuits. A particularly ambitious goal here is to design faster algorithms for solving systems of linear equations in all positive-semidefinite matrices, which would have immediate applications for basically all problems in numerical linear algebra.