EAGER: New Graph and CSP Algorithms Based on Spectral and SDP Techniques

EAGER：基于谱和 SDP 技术的新图和 CSP 算法

• 批准号: 1655215
• 负责人: Luca Trevisan
• 金额: $ 10万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1655215&HistoricalAwards=false
• 关键词: EAGER; New; Graph; CSP; Algorithms

Techniques from linear algebra have been successful in the development of algorithms for combinatorial problems, especially graph problems, with applications in data analysis, natural language processing, and network science, among others. Such algorithms are known as "spectral" algorithms. Google's PageRank algorithm is an example of a spectral algorithm."Semidefinite programming" (abbreviated SDP) is a technical tool that subsumes spectral algorithms and which has led to several rigorous results and some preliminary practical algorithmic applications. There is reason to believe that further progress could break through certain technical barriers and provide the solution to long-standing open problems. This project explores various approaches that could lead to such breakthroughs. The PI will also continue his ongoing expository work, which has made recent results in this area more accessible to a wider audience. Results from this project have the potential for a broad impact in pure mathematics and the theory of optimization; such a "mathematical technology transfer" will be facilitated by the fact that this project will overlap with a special program on Pseudorandomness at the Simons Institute for the Theory of Computing, co-organized by the PI, and a special program on Optimization also at the Simons Institute, that the PI will be a participant in. Both programs will host scholars from areas outside theoretical computer science whose interests overlap with the potential outcomes of this project.The PI will investigate promising applications of semidefinite programming to graph partitioning problems, to constraint satisfaction problems, and to the Unique Games Conjecture, including the possibility of Lasserre hierarchy SDP relaxations to refute the Unique Games Conjecture, a core open problem in computational complexity theory. In order to avoid or break known barriers to progress, the PI will investigate the power of Lasserre hiearchy relaxations to approximate the sparsest cut problem in special classes of graphs, and the power of Lasserre hierarchy SDP relaxations for constraint satisfaction problems. Spectral methods, which are a special case of Semidefinite Programming, will be used to analyze distributed algorithms, and new types of graph sparsifiers. Outcomes of the project may have applications in computational complexity theory, the theory of pseudorandomness, graph theory, data analysis, and network science.

来自线性代数的技术在组合问题特别是图问题的算法开发中取得了成功，并在数据分析、自然语言处理和网络科学等方面得到了应用。这种算法被称为“谱”算法。Google的PageRank算法就是谱算法的一个例子。半定编程(简称SDP)是一个包含谱算法的技术工具，它已经产生了几个严格的结果和一些初步的实际算法应用。有理由相信，进一步的进展可能会突破某些技术壁垒，为长期悬而未决的问题提供解决方案。这个项目探索了各种可能导致这种突破的方法。国际和平研究所还将继续他正在进行的说明性工作，这使得这一领域的最新成果更容易为更广泛的受众所了解。这一项目的结果有可能对纯数学和最优化理论产生广泛的影响；由于该项目将与西蒙斯计算理论研究所的伪随机性特别计划和西蒙斯研究所的优化特别计划重叠，这一事实将促进这种“数学技术转让”，西蒙斯计算理论研究所是该计划的联合组织，西蒙斯研究所也将参与该计划。这两个项目都将邀请来自理论计算机科学以外领域的学者，他们的兴趣与这个项目的潜在结果重叠。PI将研究半定规划在图划分问题、约束满足问题和唯一博弈猜想中的有前途的应用，包括拉瑟尔层次SDP放松来反驳唯一博弈猜想的可能性，这是计算复杂性理论中的一个核心开放问题。为了避免或打破已知的进展障碍，PI将研究Lasserre层次SDP松弛方法在特殊图类中逼近最稀疏割问题的能力，以及Lasserre层次SDP松弛方法在约束满足问题上的能力。谱方法是半定规划的一个特例，它将被用来分析分布式算法和新型的图稀疏器。该项目的成果可能在计算复杂性理论、伪随机性理论、图论、数据分析和网络科学中得到应用。

项目成果

Find Your Place: Simple Distributed Algorithms for Community Detection

找到你的位置：用于社区检测的简单分布式算法

• DOI: 10.1137/1.9781611974782.59
• 发表时间: 2017
• 期刊: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: Beeehetti, Luca;Clementi, Andrea;Natale, Emanuele;Pasquale, Francesco;Trevisan, Luca
• 通讯作者: Trevisan, Luca

Optimal Lower Bounds for Sketching Graph Cuts

绘制图形切割的最佳下界

• 发表时间: 2019
• 期刊: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Carlson, Charles;Kolla, Alexandra;Srivastava, Nikhil;Trevisan, Luca
• 通讯作者: Trevisan, Luca

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

• DOI: 10.1145/3055399.3055412
• 发表时间: 2016-11
• 期刊: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Pasin Manurangsi

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification

• DOI: 10.1137/1.9781611975031.85
• 发表时间: 2017-07
• 作者: N. Srivastava;L. Trevisan

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

• DOI: 10.1137/1.9781611974782.58
• 发表时间: 2016-04
• 期刊: Internet Mathematics
• 作者: Michele Borassi;P. Crescenzi;L. Trevisan