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

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.