A unique game problem depends on three parameters, two constants and and an integer .
Input: a bunch of 2-variable linear equations mod . We want to decide between the following two events:
- There is an assignment satisfying a fraction of equations.
- No assignment satisfies more than a fraction of equations.
Note that there is an implicit graph there, and constraints can be expressed in the form where is a bijection.
This is different from Ryan O’Donnell’s definition of MAX BIJECTION. But there is a reduction from MAX BIJECTION to our class of linear problems (due to O’Donnell et al., relies on the KKL theorem).
1. Known approximation algorithms
Charikar, Makarychev and Makarychev give an algorithm that satisfies fraction of equations. So if , half the constraints are satisfied. So unique games are easy when is very small.
If the constraint graph is an expander, there is an algorithm, AKKSTV, which satisfies fraction of equations. So unique games are easy when the constraint graph is an expander.
Both algorithms are based on SDP relaxations.
2. Charikar et al. method
2.1. The SDP relaxation
For the first one (see Claire Mathieu’s lecture nr 4 and Comment), for each variable , use vectors .
Intention: if gets value , set and if (i.e. all vectors are -dimensional). So we put the following constraints
an choose objective function (to be maximized)
Think of orthogonal vectors associated with a variable (e.g. vertex) as forming a fan. A high score implies that neighboring fans are correlated, but if the graph is large, remote fans are not correlated any more, so it is not obvious how to extract an assignment of variables from geometry.
The rounding procedure amounts to projecting along a random Gaussian direction . Let denote the dimension of the SDP solution (). The random variables are independant and normal Gaussian. For each , we want to assign which maximizes . The analysis gets a bit simpler if instead, we look at all values such that and pick one randomly. Here, .
If picks , then, with conditional probability , picks .
3. Case of expanders
One is tempted by a propagation algorithm, but this does not work. Even a small fraction of ill-labelled edges spoils everything for a general graph. Things are a bit better for expanders.
Lemma 1 If and average correlation on edges is , then random pairs are correlated, i.e. there exists a bijection of such that
This suggest to round as follows. Pick randomly, pick value with probability (recall that ). For all other , pick a value by identifying correlating matching (it is unique if it exists).
Proof: of Lemma. Use vectors to write a candidate vector incorporating edge/pairs of vertices correlations, and substitute it into . To get a single vector out of a fan, use tensor product and sum up. Then take inner product with a random vector to get .
4. More on expansion and unique games
When is this SDP not tight ? DKSV construct a graph (noisy hypercube) such that locally, things look very correlated, but there is no global correlation. David Steurer will discuss his joint work with Raghavendra on small sets expansion and how this implies UGC.