Algorithmic Results for Unique Games

Опубликовано 17 августа 2016, 22:32

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-\epsilon 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.