Computer Science/Discrete Mathematics Seminar I

Unique games were introduced by Uriel Feige and Laszlo Lovasz. We are given a graph G, a set of labels [k] = {1,...,k}, and permutations pi_{uv} on the set [k] (for all edges (u,v)). Our goal is to find an assignment of labels to variables x(u) (for all vertices u) that maximizes the number of satisfied constraints x(v) = pi_{uv}(x(u)) (for edges (u,v)). Given an instance where all constraints are satisfiable, it is easy to find such a satisfying assignment. Given an instance where 1-epsilon constraints are satisfiable, the Unique Games Conjecture (UGC) of Khot says that it is hard to satisfy even delta fraction of the constraints (for k large enough). This conjecture has attracted a lot of recent attention since it is has been shown to imply hardness of approximation results for several important problems that were difficult to approach by other means. We present new approximation algorithms for unique games that satisfy roughly k^{-epsilon/2} and 1 - O(sqrt{epsilon log k}) fraction of all constraints if 1 - epsilon fraction of all constraints is satisfiable. These results show limitations on the hardness bounds acheivable using UGC. In particular, they disprove a stronger version of UGC that was conjectured in a recent paper. Somewhat surprisingly, even a slight improvement of our results (beyond low order terms) will disprove the unique games conjecture. This is joint work with Moses Charikar and Konstantin Makarychev.