Classical algorithms for many important graph primitives were designed at a time when the conventional notion of efficiency was polynomial running time. However, many of today's applications involve graphs consisting of millions, or even billions, of nodes. On these massive inputs, practical algorithms must run in time that is as close to linear as possible in the size of the input.
The spectral approach to designing graph algorithms views the instance graph as a matrix and makes use of the algebraic properties of the corresponding linear operator. Recently, research in this area has led to the design of faster spectral algorithms for many essential graph problems, such as electrical flow, maximum flow and graph partitioning in undirected graphs. The goal of this project is to develop a novel algorithmic approach by combining spectral methods and the idea of regularization from optimization. Regularization is a mechanism for modifying a given optimization problem to make it more amenable to known algorithms without changing its salient characteristics. Surprisingly, many of the recent breakthroughs in the design of fast spectral algorithms can be viewed as applying different types of regularization. This research aims to exploit this interpretation to design algorithms that are faster, simpler to analyze and easier to implement. Another aim of this research is to integrate different perspectives on regularization from Machine Learning, Statistics and Convex Optimization, to create new bridges between these fields and the design of algorithms.
Due to the practical importance of the graph problems under consideration, the work will also focus on empirically evaluating the algorithms designed. These evaluations will be disseminated to the relevant audiences to maximize the impact of the award. Moreover, because this project aims to develop new fundamental techniques in the design of algorithms, a particular effort will be devoted to incorporating material from this research into the PI's teaching activity and to preparing educational material for the public.
