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

线性代数的技术在组合问题，特别是图问题的算法开发中取得了成功，并在数据分析、自然语言处理和网络科学等领域得到了应用。这种算法被称为“谱”算法。b谷歌的PageRank算法是光谱算法的一个例子。“半定规划”（简称SDP）是一种包含谱算法的技术工具，它已经导致了一些严格的结果和一些初步的实际算法应用。有理由相信，进一步的进展可以突破某些技术障碍，解决长期悬而未决的问题。这个项目探索了可能导致这种突破的各种方法。PI还将继续他正在进行的说明性工作，这使得该领域的最新成果更容易为更广泛的受众所了解。这个项目的结果可能对纯数学和最优化理论产生广泛的影响；这样的“数学技术转移”将被这样一个事实所促进：这个项目将与由PI共同组织的Simons Institute for the Theory of Computing的一个关于伪随机的特别项目，以及同样由PI参与的Simons Institute的一个关于优化的特别项目重叠。这两个项目都将接待来自理论计算机科学以外领域的学者，他们的兴趣与本项目的潜在成果重叠。PI将研究半定规划在图划分问题、约束满足问题和唯一博弈猜想中的有前途的应用，包括用Lasserre层次SDP松弛来反驳唯一博弈猜想的可能性，这是计算复杂性理论中的一个核心开放问题。为了避免或打破已知的进展障碍，PI将研究Lasserre层次松弛在特殊图类中近似最稀疏切问题的能力，以及Lasserre层次SDP松弛在约束满足问题中的能力。谱方法是半定规划的一种特殊情况，将用于分析分布式算法和新型图稀疏器。该项目的成果可应用于计算复杂性理论、伪随机理论、图论、数据分析和网络科学。

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.