Algorithmic Results for Unique Games

December 1, 2010
Alexandra Kolla | Microsoft Research

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 present a polynomial time algorithm which, given a 1-ε satisfiable instance of UG on an expander graph, recovers a good labelling (that satisfies more than 99% of the constraints). We will also present several extensions of the previous algorithm for expanders, including the recent breakthrough of Arora-Barak-Steurer who give a sub-exponential time algorithm for arbitrary instances of Unique Games.

The talk is based on joint works with Arora, Khot, Steurer, Tulsiani, Vishnoi, Y. Makarychev and K. Makarychev.

Speaker Details

Alexandra Kolla is a postdoc at Microsoft Research here in Redmond. Before that, she was at the Institute for Advanced study. She got her Phd at UC Berkeley.