עדן כלמטץ'

In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1 - ε) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(ε√ log n log k) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.