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

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

基本信息

  • 批准号:
    1111109
  • 负责人:
  • 金额:
    $ 97万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2011
  • 资助国家:
    美国
  • 起止时间:
    2011-09-01 至 2017-08-31
  • 项目状态:
    已结题

项目摘要

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算法),对随机过程的理解以及由此衍生的算法,纠错码的构建,去随机化,凸优化,机器学习等等。虽然拉普拉斯算子的特征值和特征向量捕捉了图的结构的惊人数量,主要研究人员和其他研究人员最近的工作表明,理论计算机科学家只触及了表面,如果他们愿意扩大他们的研究,将其扩展到研究拉普拉斯算子的更一般的代数性质,而不仅仅是其特征值结构,在这个奖项下,主要研究人员将在参与这项提案的三所大学建立一个研究计划,以开发这样的理论及其应用。这一计划有可能在计算机科学的一系列理论和应用领域提供变革性的进步,包括:* 基础图问题的更快算法,如最大流,最小割,最小成本流,多商品流,近似稀疏割,生成随机生成树,以及构建低拉伸生成树。更好的数据分析算法,以及独特博弈猜想的潜在应用。更快的算法,用于解决广泛类别的重要线性系统,包括顺序和并行。网络中信息传播的更快分布式算法。有向图的谱和代数图论,基于微分几何的思想。新的量子算法解决了一大类问题,这些问题对经典计算机来说似乎很难解决。基于计算机科学和组合学的思想,解决量子物理问题的新技术。主要研究人员还将通过开发课程,培训本科生和研究生,并将这些想法介绍给其他领域的科学家来传播这些技术。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Jonathan Kelner其他文献

Learning Mixtures of Gaussians Using Diffusion Models
使用扩散模型学习高斯混合
  • DOI:
    10.48550/arxiv.2404.18869
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Khashayar Gatmiry;Jonathan Kelner;Holden Lee
  • 通讯作者:
    Holden Lee

Jonathan Kelner的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Jonathan Kelner', 18)}}的其他基金

Collaborative Research: AF: Medium: Foundations of Structured Optimization
合作研究:AF:媒介:结构化优化的基础
  • 批准号:
    1955217
  • 财政年份:
    2020
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
CAREER: Geometric Techniques for Algorithm Design
职业:算法设计的几何技术
  • 批准号:
    0843915
  • 财政年份:
    2009
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant

相似国自然基金

水稻穗粒数调控关键因子LARGE6的分子遗传网络解析
  • 批准号:
  • 批准年份:
    2022
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
量子自旋液体中拓扑拟粒子的性质:量子蒙特卡罗和新的large-N理论
  • 批准号:
  • 批准年份:
    2020
  • 资助金额:
    62 万元
  • 项目类别:
    面上项目
甘蓝型油菜Large Grain基因调控粒重的分子机制研究
  • 批准号:
    31972875
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
Large PB/PB小鼠 视网膜新生血管模型的研究
  • 批准号:
    30971650
  • 批准年份:
    2009
  • 资助金额:
    8.0 万元
  • 项目类别:
    面上项目
基因discs large在果蝇卵母细胞的后端定位及其体轴极性形成中的作用机制
  • 批准号:
    30800648
  • 批准年份:
    2008
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
LARGE基因对口腔癌细胞中α-DG糖基化及表达的分子调控
  • 批准号:
    30772435
  • 批准年份:
    2007
  • 资助金额:
    29.0 万元
  • 项目类别:
    面上项目

相似海外基金

Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks
合作研究:AF:媒介:大规模网络中匿名通信的基础
  • 批准号:
    2312241
  • 财政年份:
    2023
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks
合作研究:AF:媒介:大规模网络中匿名通信的基础
  • 批准号:
    2312242
  • 财政年份:
    2023
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Medium: Foundations of Anonymous Communication in Large-Scale Networks
合作研究:AF:媒介:大规模网络中匿名通信的基础
  • 批准号:
    2312243
  • 财政年份:
    2023
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Nonconvex Methods and Models for Learning: Towards Algorithms with Provable and Interpretable Guarantees
AF:大型:协作研究:非凸学习方法和模型:走向具有可证明和可解释保证的算法
  • 批准号:
    1704656
  • 财政年份:
    2017
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Nonconvex Methods and Models for Learning: Toward Algorithms with Provable and Interpretable Guarantees
AF:大型:协作研究:非凸学习方法和模型:具有可证明和可解释保证的算法
  • 批准号:
    1704860
  • 财政年份:
    2017
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Algebraic Proof Systems, Convexity, and Algorithms
AF:大型:协作研究:代数证明系统、凸性和算法
  • 批准号:
    1565235
  • 财政年份:
    2016
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Algebraic Proof Systems, Convexity, and Algorithms
AF:大型:协作研究:代数证明系统、凸性和算法
  • 批准号:
    1565264
  • 财政年份:
    2016
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Medium: Collaborative research: Advanced algorithms and high-performance software for large scale eigenvalue problems
AF:中:协作研究:大规模特征值问题的先进算法和高性能软件
  • 批准号:
    1505970
  • 财政年份:
    2015
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Large: Collaborative Research: Reliable Quantum Communication and Computation in the Presence of Noise
AF:大型:协作研究:噪声存在下的可靠量子通信和计算
  • 批准号:
    1629809
  • 财政年份:
    2015
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
AF: Medium: Collaborative research: Advanced algorithms and high-performance software for large scale eigenvalue problems
AF:中:协作研究:大规模特征值问题的先进算法和高性能软件
  • 批准号:
    1510010
  • 财政年份:
    2015
  • 资助金额:
    $ 97万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了