Merging techniques for combinatorial optimization: Spectral Graph Theory and Semidefinite Programming

  • Alexandra Kolla | UC Berkeley

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.

Speaker Details

I am a fifth – year graduate student at UC Berkeley. My advisor is Umesh Vazirani. I was an intern at MSR-NE till December. I am interested in algorithms, complexity theory and combinatorial optimization. My work specifically focuses on spectral graph theory and semidefinite programming.

Watch Next