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

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

• 批准号: 1111270
• 负责人: Shanghua Teng
• 金额: $ 72.47万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1111270&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.

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