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

来自线性代数的技术已经成功地开发了组合问题的算法，特别是图形问题，并应用于数据分析，自然语言处理和网络科学等。这样的算法被称为"谱"算法。Google的PageRank算法是光谱算法的一个例子。"半定规划"（简称SDP）是一种技术工具，它包含谱算法，并导致了一些严格的结果和一些初步的实际算法应用。有理由相信，进一步的进展可以突破某些技术障碍，为长期悬而未决的问题提供解决办法。该项目探讨了可能导致此类突破的各种方法。PI还将继续其正在进行的临时工作，这使得更广泛的受众更容易获得这一领域的最新成果。从这个项目的结果有可能在纯数学和优化理论的广泛影响;这种"数学技术转让"将由于以下事实而得到促进：该项目将与西蒙斯计算理论研究所的一个关于伪随机性的特别计划（由PI共同组织）和一个关于优化的特别计划（也在西蒙斯研究所）重叠，PI将参与其中。这两个项目都将接待来自理论计算机科学以外领域的学者，他们的兴趣与本项目的潜在成果重叠。PI将研究半定规划在图划分问题、约束满足问题和唯一博弈猜想中的有希望的应用，包括拉瑟尔层次SDP松弛来反驳唯一博弈猜想的可能性，计算复杂性理论中的一个核心开放问题。 为了避免或打破已知的进展障碍，PI将研究拉瑟尔层次松弛的能力，以近似特殊类图中的稀疏割问题，以及拉瑟尔层次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.