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 constraints, where $n$ is the
number of variables. For sufficiently large alphabets, it improves an algorithm
of Khot (STOC'02) that satisfies a constant fraction of
constraints in unique games of value $1-c/(k^{10}(\log k)^5)$,
where $k$ is the size of the alphabet. We also present
a simpler algorithm for the special case of unique
games with linear constraints, and a combinatorial algorithm
for the general case.
Finally, we present a simple approximation algorithm for 2-to-1 games.
Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an epsilon fraction of constraints. We show that a strong generalization of the conjecture fails. Namely, we show that, given a system of constraints and the promise that there is an assignment that satisfies a 1-1/O((log n)^3) fraction of constraints, we can find in polynomial time an assignment that satisfies 99% of the constraints. If the constraints are linear, then given a system and the promise that a 1-1/O(log n) fraction of constraints are satisfiable, we can satisfy a 99% fraction in polynomial time. We also show weaker results about "2-to-1 Games."
We present a polynomial time algorithm that,
given a unique game of value $1-c/\log n$, satisfies
a constant fraction of constraints, where $n$ is the
number of variables.
This improves an algorithm of Trevisan (ECCC TR05-34), that
satisfies a constant fraction of constraints in unique games of value $1-c/(\log n)^3$
and, for sufficiently large alphabets, it improves an algorithm
of Khot (STOC'02) that satisfies a constant fraction of
constraints in unique games of value $1-c/(k^{10}(\log k)^5)$,
where $k$ is the size of the alphabet.
The result presented in this note will be incorporated in a later
version of ECCC TR05-34.
