### Revision(s):

__
Revision #1 to TR05-034 | 18th September 2005 00:00
__
#### Approximation Algorithms for Unique Games

**Abstract:**
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.

### Paper:

__
TR05-034 | 5th April 2005 00:00
__

#### Approximation Algorithms for Unique Games

**Abstract:**
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."

### Comment(s):

__
Comment #1 to TR05-034 | 13th May 2005 20:52
__
**Abstract:**
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.