**1. An times polylog-approximation for coloring -colorable graphs **

1. Reduce degree as before.

2. Recall the SDP relaxation we used on wednesday. Minimize under constraints , . Today, we merely change the rounding procedure.

3. Rounding. Let be well-chosen values, . While max degree , pick a random Gaussian vector . Consider the affine (i.e. does not go through the origin) hyperplane normal to defined by . It isolates a part of the vertices,

which need not form an independant set. So take

color in one color and remove it.

4. Color remainder with colors.

Analysis. Since the Gaussian density is rotation invariant and a tensor product of one variable Gaussians,

Since , where is unit and orthogonal to . So , where the normal Gaussian random variable is independant from . So the conditional probability

where is the maximum degree. Choose so that . We shall use the rough estimates, for

The upper bound gives

Using the lower bound, we get

where is the current number of vertices (remember that we keep discarding vertices once colored). Markov inequality applied to gives

If this happens, we do nothing. Else, we remove , and decreases at least by a factor .

How many colors have been used ? At each successful round, we win a factor , so the number of effective rounds is . So the total number of colors is at most

Take and this is .

Runtime is polynomial, since the expectation of the number of idle rounds is.

Best known approximation is (recent result of S. Arora, based on a better SDP).

**2. Unique games **

** 2.1. The problem **

A *unique game* involves variables with values in . binary constraints (i.e. constraint involves 2 variables). In each constraint involving and , the value of is *uniquely* determined by the value of . Goal: maximize number of satisfied constraints.

Example 1mod is a unique constraint. So systems of 2-variable linear equations over constitute unique games.

In fact, the unique games problem Karp-reduces to the linear unique games problem.

Note that the question wether , i.e. wether the set of constraints has a feasible assignment, has an easy answer: try a value for variable , and propagate it around using uniqueness. On the other hand, the question wether is close to or not seems hard.

** 2.2. Trevisan’s algorithm **

Theorem 1There is an algorithm which, when applied to a unique game whose , outputs an assignment satisfying constraints.

The statement differs from previous ones, in that its scope is reduced: it applies only to special instances (those whose is close to the maximum ) but gives an approximation factor close to .

A similar theorem holds for MAX CUT. Both results are due to Luca Trevisan, 2005, [T].

** 2.3. The SDP **

There is an implicit graph : vertices correspond to variables and edges to constraints. Each edge comes with the table of the permutation . Or a permutation matrix . Unknowns will be vectors (of unspecified dimension), indexed by pairs where is a vertex, . Change notation: abbreviate . Every vertex must have a single color, so let us impose

so that integral solutions correspond to vertex coloring. A coloring also satisfies for and for all . For every edge , the corresponding constraint reads (for feasible solutions, i.e. integral solutions of previous equations), so we want to maximize

Trick: we add constraints which provide us with a metric. The reason is that we are dealing with a multicutting problem and we want to mimic the technique for designing multicuts from balls in a metric.

These extra constraints are

They are satisfied by feasible solutions. This is our SDP.

** 2.4. The algorithm **

1. Solve SDP relaxation.

2. Partition into balls of radius at most ( well chosen).

For all edges , let

This is a metric on .

While is not empty, take arbitrary vertex . Define

Choose to minimize where

Let . Add to the partition, remove from .

Choose .

3. Rounding. Now we assign colors to vertices. For each ball, let us assign a color to the center , by picking it at random using the probability distribution . For other vertices in the ball, choose their color to minimize .

** 2.5. Analysis **

By construction, SDP is a relaxation.

Lemma 2Assume there is an assignment satisfying constraints. Then

*Proof:* We have:

When spans , by definition of unique games also spans , so equals . We use the first set of constraints of the SDP to infer . Summing over all constraints, is just minus the value of the SDP. The SDP is a relaxation, so its value is at least , and so is at most .

The next three lemmas follow closely our analysis of the multicut algorithms.

*Proof:* Let be the center of the ball. Assume, up to perturbating , that takes distinct values for all . Then is continuous, increasing, and piecewise linear, and it is easy to see that at every where is differentiable. Let . We have: at every where is differentiable.

By a variant of the mean value theorem, there exists an where is differentiable and such that is less than or equal to . Thus the ball added to the partition will also satisfy

Now, by definition of we have . On the other hand, is at most . Since is the shortest path metric defined by , we have . By definition of , we infer . Combining yields the lemma.

Lemma 4Assume that there exists an assignment satisfying constraints. Then the total number of edges not inside parts of the partition is at most .

*Proof:* Every time the algorithm picks a ball as a part of the partition, the number of edges then discarded is . The total number is thus . By Lemma 3, this is at most . Using the definition of and the fact that ,

By Lemma 2, is at most . Combining gives the result.

Lemma 5Let and let . Then there is at most one index such that .

*Proof:* Consider and for . By the last set of SDP constraints we can write:

Summing gives . Remembering the SDP orthogonality constraints, we can write , and, applying the SDP triangular inequality constraints, . Combining gives . Thus at most one of can be such that .

Here is the most important step.

Lemma 6Let be a path between two vertices and . Choose label for with probability , and infer a label for by propagating labels along the path so that all constraints are satisfied. Then, with probability at least , the resulting label minimizes .

*Proof:* Let be the set of ‘s such that does not minimize . We want to upper bound . By Lemma 5, if then . By the SDP triangular inequality constraints,

where denotes the label of obtained by labeling with and propagating labels along the path so that all constraints are satisfied. The probability that the propagated label does not coincide with the assigned label is

The inner summation can be bounded by . By definition of unique games, when spans , also spans . Thus:

This implies the lemma.

Lemma 7Let be a ball of the partition. Let where and . Then the probability that constraint is not satisfied by the algorithm is at most .

*Proof:* Let be a shortest path from to , and consider the path from to . If the algorithm labels according to propagation along path and according to propagation along path , then constraint is satisfied. Apply Lemma 6 twice, to those two paths: since is a shortest path, the probability that the algorithm labels differently than by propagating along path is at most . The probability that the algorithm labels differently than by propagating along path is at most .

Lemma 8Assume that there exists an assignment satisfying constraints. Then at most constraints have .

*Proof:* By Lemma 2 we have: . Since each term is non-negative, the number of terms greater than is at most .

To complete the proof of the Theorem, it only remains to bound the number of constraints not satisfied. There are three ways for constraints to not be satisfied: by Lemma 4, at most constraints are not inside balls of the partition; by Lemma 7, at most constraints are long; and by Lemma 8, in expectation, there are at most short constraints inside balls of the partition, for which propagation does not coincide with the choice of the labeling algorithm. This sums to

since .

** 2.6. The Unique Games Conjecture **

Trevisan’s Theorem 1 is significant only when . For fixed , can one find a fixed and an algorithm which, when applied to a unique game whose , outputs an assignment satisfying ? Roughly speaking, Subhash Khot’s *Unique Games Conjecture* claims that this is impossible. More precisely, the conjecture states that for every and , there exists a such that the following *gap problem* is NP-complete.

*Given a unique game with labels such that or , decide which of the two cases holds.*

For a slightly larger class of problems, Projection games, the corresponding gap problem is known to be NP-complete. So the Unique Games Conjecture (UGC) seems close to present knowledge. Nevertheless, is has so many striking consequences that it is hard to believe in it. For instance, it implies that the Goemans-Williamson approximation threshold 0.878… is sharp, S. Khot, G. Kindler, E. Mossel, R. O’Donnell 2007, [KKMO], see the first lecture in this series.

For more on UGC, see Khot’s talk in Cambridge this afternoon and the course of Sanjeev Arora and David Steurer in Paris next week.

** References **

[KKMO] Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O’Donnell, Ryan; * Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?* SIAM J. Comput. **37** (2007), no. 1, 319–357.

[T] Trevisan, Luca; * Approximation Algorithms for Unique Games.* Proc. of the 46th IEEE FOCS, 2005.

Could you clarify the beginning of the chapter 2.3. The SDP?

I did not completely understand the setting: for variables we picked {k} vectors for each vertex {u} in the graph. But why? What do the vectors {u_i} refer to? Their length seems not to be of importance, not even defined. Why does

\displaystyle \begin{array}{rcl} \sum_{i=1}^{k}|u_i|^2 =1, \end{array}

impose that every vertex has a single colour? And what does an integral solution mean?

BTW, there is a missprint:

“Unknown will vectors {v_{ui}}, {u} vertex, {i\in\{1,\ldots,k\}}.”

-> probably “Unknowns will be vectors etc”.

Dear Riikka,

Thanks for proofreading these notes and pointing to mistakes in the notes that make them impossible to understand.

The first step in an SDP approach to an optimisation problem is to embed the given problem in a semidefinite program. This means mapping unknowns of the combinatorial problem to unknowns of the semidefinite program in such a way that objective functions coincide.

Here, the unknowns of the combinatorial problem are k-colorings. Suppose we view a k-coloring as a vector in R^n, whose components are integers between 1 and k. When relaxing the integrality assumption, the number k, which is essential for the combinatorial problem, disappears. The optimum of the SDP does not depend on k. This does not seem to be a good idea.

In order to freeze k in the SDP, Luca Trevisan had the idea to include it as a dimension. He chooses unknowns of the SDP to be nk-tuples of vectors. Note that the dimension of the vectorspace where these vectors live is unspecified. This is a rule for SDP’s: the true unknown is the Gram matrix X (whose entries are pairwise inner products) of the collection of vectors. Individual vectors (columns of a matric V) appear only when one expresses X as X=V^top V, they are defined only up to rotation, and their dimension, the rank of X, is apriori unknown.

A coloring v (i.e. a {1,…,k}-valued function on vertices) is mapped to an nk-tuple of vectors as follows: given a vertex u and a color i, set u_i to be the vector with one component, equal to zero unless v(u)=i, in which case it is 1.

The objective function is the number of satisfied constraints, which can be rewritten as

\sum_{e=uv}\sum_{i=1}^{k}u_i \cdot v_{\pi_{e}(i)}.

Next, one collects semidefinite constraints satisfied by such very special k-tuples of vectors.

1. For all vertices u, v and colors i, j, inner product u_i . v_j is nonnegative.

2. If i and j are distinct colors, and u is a vertex, then the inner product u_i . u_j vanishes.

3. For every vertex u, only one of the vectors u_i is non zero, so \sum_{i=1}^k |u_i|^2 =1.

4. Triangle inequalities.

The collection of these constraints constitutes the SDP.

Sincerely,