AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond

AF：大型：协作研究：代数图算法：拉普拉斯算子及其他算法

• 批准号: 1111257
• 负责人: Daniel Spielman
• 金额: $ 77.28万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1111257&HistoricalAwards=false
• 关键词: AF; Large; Collaborative; Research; Algebraic

This project will exploit algebraic properties of operators associated with graphs in an integrated set of research and educational activities designed to develop new mathematical and algorithmic techniques; apply these to the solution of real-world problems and longstanding theoretical questions in mathematics, computer science, biology, and physics; and make these techniques broadly known and accessible to students, researchers, and practitioners in many fields. This research has its origins in spectral graph theory, which studies how the eigenvalues and eigenvectors of the graph Laplacian (and other related matrices) interact with the combinatorial structure of the graph. Spectral graph theory has been one of the great success stories in both the theory and practice of algorithm design. It has led to fundamental advances in graph partitioning, web search (notably including Google's PageRank algorithm), the understanding of random processes and the algorithms derived from them, the construction of error correcting codes, derandomization, convex optimization, machine learning, and many others. While the eigenvalues and eigenvectors of the Laplacian capture a striking amount of the structure of the graph, they certainly do not capture all of it. Recent work by the principal investigators and other researchers suggests that theoretical computer scientists have only scratched the surface of what can be done if they are willing to broaden their investigation, extending it to study more general algebraic properties of the Laplacian than just its eigenvalue structure, and more general operators than just the Laplacian. Under this award, the principal investigators will build a research program across the three universities involved in this proposal to develop such a theory and its applications. This initiative has the potential to provide transformative advances in a range of theoretical and applied areas of computer science, including: * Faster algorithms for fundamental graph problems, such as Maximum Flow, Minimum Cut, Minimum Cost Flow, Multicommodity Flow, approximating Sparsest Cut, generating random spanning trees, and constructing low-stretch spaning trees. * Better algorithms for the analysis of data, with potential applications to the Unique Games Conjecture. * Faster algorithms for solving broad classes of important linear systems, both sequentially and in parallel. * Faster distributed algorithms for information dissemination in networks. * A spectral and algebraic graph theory for directed graphs, based on ideas from differential geometry. * Novel quantum algorithms for a large class of problems that appear to be hard for classical computers. * New techniques for problems in Quantum Physics based on ideas developed in Computer Science and Combinatorics. The principal investigators will also work to disseminate these techniques by developing courses, training undergraduate and graduate students, and introducing these ideas to scientists in other fields.

该项目将在一系列旨在开发新的数学和算法技术的研究和教育活动中利用与图形相关的运算符的代数性质；将这些应用于解决数学、计算机科学、生物学和物理学中的现实世界问题和长期存在的理论问题；并使这些技术为许多领域的学生、研究人员和从业者广泛了解和使用。这项研究起源于谱图理论，它研究图的拉普拉斯矩阵(以及其他相关矩阵)的特征值和特征向量如何与图的组合结构相互作用。谱图理论是算法设计理论和实践中最成功的案例之一。它导致了图划分、网络搜索(尤其包括Google的PageRank算法)、对随机过程及其派生算法的理解、纠错码的构造、去随机化、凸优化、机器学习等许多方面的基本进步。虽然拉普拉斯的特征值和特征向量捕捉到了图形结构的惊人数量，但它们肯定不能捕捉到全部结构。主要研究人员和其他研究人员最近的工作表明，如果理论计算机科学家愿意扩大他们的研究范围，将其扩展到研究拉普拉斯算子的更一般的代数性质，而不仅仅是它的特征值结构，以及比拉普拉斯算子更一般的算子，那么他们只触及了皮毛。根据这一奖项，主要研究人员将在参与这项提议的三所大学之间建立一个研究计划，以开发这样的理论及其应用。这一倡议有可能在计算机科学的一系列理论和应用领域提供变革性的进展，包括：*用于基本图问题的更快的算法，例如最大流、最小割、最小成本流、多商品流、近似最稀疏割、生成随机生成树以及构造低伸展的跨度树。*更好的数据分析算法，潜在地应用于独特的游戏猜想。*更快的算法，用于顺序和并行地求解广泛类别的重要线性系统。*更快的分布式算法，用于网络中的信息传播。*有向图的谱和代数图论，基于微分几何的思想。*针对一大类似乎对经典计算机来说很难的问题的新量子算法。*基于计算机科学和组合学中发展的思想的量子物理问题的新技术。主要研究人员还将努力通过开发课程、培训本科生和研究生并将这些想法介绍给其他领域的科学家来传播这些技术。