Techniques for combinatorial optimization: Spectral Graph Theory and Semidefinite Programming

Опубликовано 6 сентября 2016, 18:29

The talk focuses on expander graphs in conjunction with the combined use of SDPs and eigenvalue techniques for approximating optimal solutions to combinatorial optimization problems. In the first part of the talk I will explain how to construct cost-effective, expanding networks by using local sparsifiers of graphs that emerge as a solution to a semidefinite program. In the second part of the talk I will show that the Unique Games Conjecture is false when the underlying constraint graph is a (spectral) expander. Namely, I will present a polynomial-time algorithm for Unique Games on expanding instances that finds a good assignment when there exists one.