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.

该项目将利用与图相关的算子的代数性质，在一套完整的研究和教育活动中，旨在开发新的数学和算法技术；将这些应用于解决现实世界的问题和数学、计算机科学、生物学和物理学中长期存在的理论问题；并使这些技术广泛地被学生、研究人员和许多领域的从业者所了解和使用。本研究起源于谱图理论，研究图拉普拉斯（及其他相关矩阵）的特征值和特征向量如何与图的组合结构相互作用。谱图理论在算法设计的理论和实践中都取得了巨大的成功。它导致了图划分、网络搜索（特别是包括b谷歌的PageRank算法）、对随机过程及其衍生算法的理解、纠错码的构建、非随机化、凸优化、机器学习等许多方面的根本性进步。虽然拉普拉斯函数的特征值和特征向量捕获了图的大量结构，但它们肯定不能捕获全部结构。主要研究人员和其他研究人员最近的工作表明，如果理论计算机科学家愿意扩大他们的研究，将其扩展到研究拉普拉斯算子的更一般的代数性质而不仅仅是它的特征值结构，以及更一般的算子而不仅仅是拉普拉斯算子，那么他们所能做的事情只是触及了表面。根据该奖项，主要研究人员将在参与该提案的三所大学建立一个研究计划，以发展这样的理论及其应用。这一举措有可能在计算机科学的一系列理论和应用领域提供变革性的进步，包括：*基本图问题的更快算法，如最大流量、最小切割、最小成本流、多商品流、近似稀疏切割、生成随机生成树和构建低拉伸生成树。*更好的数据分析算法，具有Unique Games Conjecture的潜在应用。*更快的算法来解决广泛的重要线性系统，无论是顺序的还是并行的。*更快的分布式网络信息传播算法。基于微分几何思想的有向图的谱图和代数图理论。*为经典计算机难以解决的大量问题提供新颖的量子算法。*基于计算机科学和组合学思想的量子物理问题新技术。主要研究人员还将通过开发课程、培训本科生和研究生以及将这些想法介绍给其他领域的科学家来传播这些技术。