AF: Small: New Perspectives on Special Methods for Graph Algorithms

许多重要图基元的经典算法是在效率的传统概念是多项式运行时间的时候设计的。然而，今天的许多应用程序都涉及到由数百万甚至数十亿个节点组成的图。在这些巨大的输入上，实用的算法必须在输入大小上尽可能接近线性的时间内运行。图算法设计的谱方法将实例图看作一个矩阵，并利用相应线性算子的代数性质。最近，在这一领域的研究导致了许多基本图问题的更快谱算法的设计，如无向图中的电流、最大流量和图划分。该项目的目标是通过结合谱方法和优化的正则化思想来开发一种新的算法方法。正则化是一种修改给定优化问题的机制，使其更适合已知算法，而不改变其显著特征。令人惊讶的是，最近在快速谱算法设计方面的许多突破可以被视为应用了不同类型的正则化。本研究旨在利用这种解释来设计更快、更简单的分析和更容易实现的算法。本研究的另一个目的是整合机器学习、统计学和凸优化中关于正则化的不同观点，在这些领域和算法设计之间建立新的桥梁。由于所考虑的图问题的实际重要性，工作也将侧重于经验评估所设计的算法。这些评价将分发给相关受众，以最大限度地发挥奖项的影响。此外，由于该项目旨在开发算法设计中的新基本技术，因此将特别努力将这项研究的材料纳入PI的教学活动，并为公众准备教育材料。

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.