Published: October 10, 2008

**Keywords:**complexity theory, approximation algorithms, constraint satisfaction, Unique Games

**Categories:**complexity theory, algorithms, approximation algorithms, constraint satisfaction, Unique Games

**ACM Classification:**F.2.2

**AMS Classification:**68Q17

**Abstract:**
[Plain Text Version]

A *unique game* is a type of constraint satisfaction problem with two
variables per constraint. The *value* of a unique game is the fraction
of the constraints satisfied by an optimal solution. Khot (STOC'02) conjectured
that for arbitrarily small $\gamma, \epsilon >0$ it is NP-hard to distinguish games
of value smaller than $\gamma$ from games of value larger than $1-\epsilon$.
Several recent inapproximability results rely on Khot's conjecture.

Considering the case of sub-constant $\epsilon$, Khot (STOC'02) analyzes an algorithm based on semidefinite programming that satisfies a constant fraction of the constraints in unique games of value $1-O(k^{-10}\cdot (\log k)^{-5})$, where $k$ is the size of the domain of the variables.

We present a polynomial time algorithm based on semidefinite programming that, given a unique game of value $1-O(1/\log n)$, satisfies a constant fraction of the constraints, where $n$ is the number of variables. This is an improvement over Khot's algorithm if the domain is sufficiently large.

We also present
a simpler algorithm for the special case of unique
games with *linear* constraints, and a simple approximation algorithm
for the more general class of *2-to-1* games.