Corelab Seminar
2011-2012
Alexandra Kolla (UIUC)
Spectra of Graphs and the Unique Games Conjecture
Abstract.
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.