Spectral Algorithms for Unique Games

-
Alexandra Kolla, IAS
Fine Hall 224

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, MAXCUT.In this talk, we will present a purely spectral algorithm for Unique Games (UG). Our algorithm, given a 1-\epsilon satisfiable instance of UG, recovers a good labelling (that satisfies more than 99% of the constraints). The running time of the algorithm depends exponentially on the dimension of a certain eigenspace of the underlying constraint graph. As a significant application, our algorithm is able to distinguish (in quasi-polynomial time) highly satisfiable instances of UG on underlying graphs that have been proved to be hard for a natural semidefinite programming relaxation for Unique Games (integrality gap instances), giving evidence that spectral techniques might be a more powerful tool for approximation algorithms than SDPs.