Techniques for combinatorial optimization: Spectral Graph Theory and Semidefinite Programming

2,486 views · Published 6 September 2016 · 52:01 · Indexed 12 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

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.

More from this channel