Corelab Seminar

Alexandra Kolla (UIUC)
Spectra of Graphs and the Unique Games Conjecture

Khot's Unique Games Conjecture (UGC) is one of the most central open problems in computational complexity theory. UGC asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small. Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard problems such as Vertex Cover, Max Cut.
In the first part of the talk we will describe the Unique Games problem and give an overview of the state-of-the-art algorithmic results for Unique Games. In the second part of the talk we will review some facts from spectral graph theory and discuss the somewhat surprising but also natural (in hindsight) connection between spectra of graphs and Unique Games. We will present a class of algorithms for Unique Games that use eigenvalue techniques, run efficiently, and achieve good approximation ratios for several interesting classes of Unique Games which, prior to these works, were considered to be the hardest instances.
The talk is based on several joint works with Arora, Khot, Steurer, Tulsiani, Vishnoi, Y. Makarychev and K. Makarychev.

Short Bio.
Alexandra Kolla is an assistant professor at UIUC. Before that, she was a postdoc at Microsoft Research in Redmond and at the Institute for Advanced study. She got her Phd at UC Berkeley.