The unique games conjecture and recent results

Subhash Khot is one of the great young complexity theorists in the world. He is perhaps best known for his wonderful conjecture—the Unique Games Conjecture. But also he has worked in other areas, and solved many other important problems. He just won the Waterman Award this year, formally the 2010 Alan T. Waterman Award. It is named after the first Director of NSF, and was created in 1975. Subhash joins an array of famous mathematicians including:

• Charles Fefferman, 1976
• William Thurston, 1979
• Harvey Friedman, 1984
• Herbert Edelsbrunner 1991
• Gang Tian, 1994
• Emmanuel Candes, 2006
• Terence Tao, 2008

Wonderful.

Today I want to talk about the Khot’s Unique Game Conjecture and some recent results on his conjecture.

John Cherniavsky, Senior Advisor for Research at NSF and an longtime friend of mine, just told me yesterday that Subhash recently gave a wonderful talk at NSF. John added,

“It might be appropriate to Blog about his Unique Games Conjecture work—which seems very relevant to your Blog.”

I agree. So here is my view of UGC in three acts.

Act I: The Unique Games Conjecture

Khot’s conjecture is remarkable on many levels: it is is simple to state and yet it has created a wealth of important ideas and results. Perhaps, stating a great conjecture—whether true or false—is one of best ways to advance any field. Steve Cook and Dick Karp have the P=NP? question, Juris Hartmanis the Isomorphism Conjecture, and so on. Now we have the Unique Games Conjecture of Khot.

Most of you probably know the Unique Games Conjecture, but I will give an informal definition of it anyway. I think of it as a generalization—a very clever one—of the simple problem of 2-coloring a graph. Suppose ${G}$ is an undirected connected graph. There is a linear time algorithm for testing whether the graph is 2-colorable—you probably saw it in Computing 101:

1. Pick any starting vertex ${v}$.
2. Color ${v}$ red.
3. Select any vertex ${u}$ that is yet uncolored and is adjacent to a vertex that is colored. If ${u}$ is adjacent to a red vertex, then color it green; if it is adjacent to a green vertex, then color it red.
4. Continue until all the vertices are colored.
5. The graph is 2-colorable if and only if there are no conflicts when all vertices are colored.

Khot’s idea was to change the notion of 2-colorable in several simple ways. First, he allows a fixed but arbitrary set of colors—finite of course. This sounds like it might become the general coloring problem, but his brilliance is to pull back and make it closer to 2-coloring. He notes the essence of 2-coloring is the rule: If a vertex ${v}$ is red, then any neighbor is green. Khot allows each edge to have its own rule: the key is the rule must be deterministic. If ${v}$ and ${u}$ are adjacent, then the color of one must uniquely determine the color of the other.

Generally a graph with rules restricting allowed values for the vertices on each edge is called a constraint graph—but the uniqueness makes these graphs special. It is still easy to tell whether or not such a graph can be colored so all edges rules are followed: it takes only linear time. Just take the 2-coloring algorithm and modify it slightly:

1. Pick any starting vertex ${v}$ and a color ${c}$.
2. Color ${v}$ with the color ${c}$.
3. Select any vertex ${u}$ that is yet uncolored and is adjacent to a vertex ${v}$ that is colored. Use the edge rule to color ${u}$. Note, there is no choice here once ${v}$ is selected.
4. Continue until all the vertices are colored.
5. If all the edge rules are satisfied the graph is satisfiable. If not go back to step (1) and try another color ${c'}$. If all the colors have been tried, then the graph is not satisfiable.

Still linear time, still Computing 101.

So far we have an easy problem—what is all the excitement? Why is this so important that Subhash was awarded the Waterman prize? Khot adds one final ingredient: approximation. Suppose ${G}$ is again a unique-constraint graph, but now I promise that one of two situations is true:

• There exists an assignment of colors to the vertices of ${G}$ so at least ${1-\varepsilon}$ of the edges are satisfied;
• There is no assignment of colors to the vertices of ${G}$ so more than ${\varepsilon}$ edges are satisfied.

Telling which case is true is what consists of the Unique Games Conjecture (UGC). Khot conjectured it is NP-hard to tell which is true, for large enough sets of colors and all constraint graphs. Specifically, his conjecture states that for all ${\varepsilon > 0}$ there is an ${R}$ such that if some polynomial time algorithm distinguishes the above two situations for all unique-constraint graphs with ${R}$ colors, then P = NP. The point is that allowing some edges to fail destroys the above linear time algorithm.

Act II: Applications of UGC

The beauty of the problem is it is simple, yet a very powerful problem. The ability to let each edge have its own rule allows many problems to be encoded into a UG problem. Since Khot made his conjecture in 2002 there have been many many papers proving theorems of the form:

Theorem: Obtaining a Y-approximation to problem X is as hard as solving the UG problem.

One of the best examples is the famous algorithm of Michel Goemans and David Williamson for maximum cut of a graph. If Khot’s UGC is true, then their algorithm would be essentially the best one can hope for. Pretty neat result.

Act III: Is The UGC True?

As you probably know I am unsure of P=NP, so I have similar thoughts about the UGC—perhaps stronger doubts since it is unknown whether or not solving UG is NP-hard. I do believe whether it is eventually shown to be false or not changes little about the brilliance of the conjecture. Mathematics is moved forward by great conjectures, and Khot has certainly done this for computational complexity. It takes insight, creativity of the highest order, and a bit of “guts” to make such a conjecture.

However, in recent years and now recent months there have been a series of results showing that UG problems may not be so difficult. The ideas in these beautiful papers would not have existed without the UGC, and the techniques used may be used to solve other problems—no matter what eventually happens to the UGC.

I am neither the expert nor do I have the time right now to give an exhaustive list of all the results that have been chipping away at the UGC. I would like to mention one direction in detail and just state the other more recent ones.

The first direction was a series of results by many to show that solving UG problems on expander graphs is easy. This is work of many, including: Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth Vishnoi. I apologize for not listing all, but I do plan to discuss this in more depth in the future.

A sample result is due to Konstantin Makarychev and Yury Makarychev:

Theorem: There exists a polynomial time approximation algorithm that given a ${(1 -\varepsilon)}$ satisfiable instance of Unique Games on a ${d}$-expander graph G with ${\varepsilon/\lambda_{G} \le c_{1}}$, finds a solution of cost

$\displaystyle 1 - c_{2}\frac{\varepsilon}{h_{G}}.$

where ${c_{1}}$ and ${c_{2}}$ are some positive absolute constants.

Note, ${h_{G}}$ is the normalized edge expansion constant and ${\lambda_{G}}$ is the smallest positive eigenvalue of the normalized Laplacian of the graph ${G}$. Alexandra Kolla has similar results, but as I said earlier I cannot state and compare all the known results.

There is even more recent work due to Arora, Boaz Barak, Steurer (ABS) that could be the start of the end of the UGC. They show, roughly, that any UG problem can be solved in time

$\displaystyle 2^{n^{\varepsilon}}$

for ${\varepsilon>0}$. This does not rule out the UGC being NP-hard, but it certainly shows if the UGC is true there would be great consequences.

ABS shows that if the UGC is true then either some famous NP-hard problems have subexponential time algorithms, or any reduction showing NP-hardness of the UGC must take time with a polynomial whose exponent depends on the ${\varepsilon}$ parameter, which seems to defeat local-gadget reductions used for other approximation problems. Absolutely ABS shows that there are smarter ways of solving UG problems than simple backtracking—the result shows that a general divide-and-conquer paradigm can be employed. Their result contains a new insight into the structure of any graph, one that could have far-ranging consequences beyond the important application to the UGC.

A Comment on UG on Expanders

I believe the bounds for playing UG on expanders are a bit misleading. They are right, they are deep, and they are important results. But, unless I am confused—always a possibility—we need to be careful in reading too much practicality into these results.

This is my concern. Let ${G}$ be a ${d}$-regular graph. Then, there is a trivial method to always find a solution to a UG problem with ${1/(d+1)}$ fraction of the edges satisfied. By Brook’s Theorem such a graph has a ${d+1}$ edge coloring: pick the most common color and these edges can be satisfied. Thus, if we are trying to separate a ${1-\varepsilon}$ from ${\varepsilon}$ fraction of the edges, the promise problem is meaningful only for ${\varepsilon > 1/(d+1)}$.

Thus, if we are trying to separate ${1-\varepsilon}$ from ${\epsilon}$ fraction of the edges, ${\epsilon > 1/(d+1)}$. The Makarychev and Makarychev’s theorem has a large constant ${c_{2} \approx 100}$, and

$\displaystyle 1 - c_{2}\frac{\varepsilon}{h_{G}} > \varepsilon$

forces the degree ${d}$ to be very large. Unless I am wrong, if the graph is a spectral expander, then ${d}$ must be order ${10,000}$ and in any case it must be order ${100}$.

These bounds are not extremely large by theory standards, but they do leave open the question of what happens on expander graphs of modest degree ${d}$. Perhaps a small point, but one I find interesting.

Open Problems

What happens when we try to solve the UG problem on degree-3 graphs? What values of ${\varepsilon}$ versus ${1 - \varepsilon}$ are distinguishable? What happens on other graphs of low degree? The last word may be due to Oded Goldreich:

I’m happy to see yet another application of the paradigm of decomposing any graph into parts that are rapidly mixing, while omitting relatively few edges. Let me seize this opportunity and mention the application of this paradigm in the bipartite tester for bounded-degree graphs.

He was referring to a paper by Jonathan Kelner and Aleksander Madry on generating random spanning trees, but this could apply to the Arora-Barak-Steurer breakthrough. Perhaps graph property testing techniques can shed light on the UGC.

24 Comments leave one →
1. May 5, 2010 11:34 pm

A simple example of a unique game instance comes from 3-coloring a triangulation of a 2-dimensional surface: finding a 3-coloring is the same as picking one of the six possible colorings for each triangle of the surface in such a way that each two triangles that share an edge have compatible colorings. So the graph G that you describe is the dual graph of the surface, R=6, and it seems that in this case the quantity to be approximated is the minimum number of edges of the surface such that separating the triangles at those edges decomposes the surface into 3-colorable patches. Is anything known about this special case? I imagine it might be easier when the surface has bounded genus, for instance.

2. May 6, 2010 2:44 am

Instead of Brooks’ theorem you mean Vizing’s theorem:
http://mathworld.wolfram.com/VizingsTheorem.html

3. blind one permalink
May 6, 2010 2:45 am

That is so mean of you to use the colors red and green for a 2-coloring. Don’t you know that this is the most common form of colorblindness?

May 6, 2010 5:35 am

Sorry. They were just names. Next time will use other colors.

• Math Boy permalink
May 6, 2010 7:41 am

Don’t you know that blind people can’t see colors? You should buy marbles of two sizes and mail them out to all your readers.

4. Ryan O'Donnell permalink
May 6, 2010 7:49 am

On one hand, it’s not so strange to have a natural NP-hard approximation problem solvable in time 2^{n^eps}. For example, Hastad’s famous 1996 result shows that it is NP-hard to approximate CLIQUE to a factor of n^{1-eps}, even though this problem is easily solvable in roughly 2^{n^eps} time.

On the other hand (as Boaz pointed out to me — thanks!): For Hastad’s clique problem, in some sense the “witness size” is only n^{eps}. For the [ABS] approximation algorithm for Unique Games, the witness size is still order n, which makes the result surprising.

May 6, 2010 7:59 am

Thanks for this quite useful comment.

• May 6, 2010 9:16 am

Ryan, is n the number of vertices or the number of edges?

May 6, 2010 9:18 am

One question please. It seems that UGC would be false if e was constant rather than proportionnal to n. Is that right?

May 6, 2010 10:02 am

Unique Games is always satisfiable on a tree, so one can in fact trivially satisfy a fraction $\frac{n-1}{m} \approx \frac{2}{d}$ of the constraints (where $n,m$ are the number of vertices and edges) in a d-regular graph.

May 6, 2010 1:33 pm

Thanks. Can you do better?

May 6, 2010 12:03 pm

Dick,
Like your earlier posts on meta-topics which were all wonderful, may I request a post on “Conjectures that turned out to be false but gave rise to a wealth of ideas”? I would like to take this opportunity to thank your wonderful blog, unlike any other “theory” blog!
mntsami

May 6, 2010 1:33 pm

I will have to do this. Very interesting question.

May 7, 2010 9:47 am

I’ve done a bit of research in the area, so here are a few comments that might help.

Unique games are in fact easy on ANY kind of sparse graph.

Suppose we are given a unique game on a graph $G$ with $n$ vertices and at most $\alpha n$ edges for some constant $\alpha$. If $G$ is connected, then by satisfying all of the edges on some spanning tree of $G$, we can easily satisfy at least $n-1$ of the edges. In general, as long as $G$ contains no isolated vertices, repeating this on each component of $G$ will satisfy at least $\frac{n}{2}$ edges and thus yields a $\frac{1}{2\alpha}$-approximation to the optimal solution. This proves the following:
\begin{theorem}
Let $\alpha>1$. If $\mathcal{C}_\alpha$ is the class of all unique games on graphs $G=(V,E)$ with $|E| < \alpha |V|$ and no isolated vertices, then the UGC is false for $\mathcal{C}_\alpha$.
\end{theorem}

Since graphs with low crossing number must have $|E| \in O(|V|)$, we obtain the following corollary:
\begin{corollary}
Let $\nu\geq0$. If $\mathcal{C}_\nu$ is the class of all unique games on graphs with crossing number at most $\nu$, then the UGC is false for $\mathcal{C}_\nu$. In particular, the UGC is false for planar graphs, graphs of bounded genus, etc.
\end{corollary}

UGC is also easily seen to be false on dense graphs (where $|E| \geq \beta |V|^2$ for some constant $\beta$). Proof: exercise.

Something I've been curious about is whether or not progress can be made by looking at restrictions on the allowed CONSTRAINTS rather than on the allowed GRAPHS. For example, it is known that UGC with all allowed permutations on the edges is equivalent to UGC with only permutations of the form $x_1 = ax_2 + b$ mod $p$ for a prime $p$. So instead of allowing every edge to be assigned a member of the full symmetric group, we allow each edge to be assigned a member of the Frobenius group of order $p(p-1)$, and the conjecture is unchanged. This Frobenius group has some useful properties (in particular, every element of the group, when viewed as a permutation, has 0, 1, or $p$ fixed points.)

What about subgroups of this Frobenius group? Here is a question to which I do not know the answer: what if only members of the cyclic group of order $p$ are permitted? In other words, suppose I give you a unique game with colours $1$ through $p$ where each constraint is of the form $x_1 = x_2 + b$ mod $p$. Is the problem still hard?

9. May 11, 2010 11:12 am

I jumped on Wikipedia and read the article, but it was a lot like walking through pudding: slow going and afterward I felt kinda dirty.

10. Steven Twentyman permalink
June 30, 2010 5:50 pm

Hello.

What if, in a general theory of everything kind of way, some singular human conscious had used simple Yes(I should feel guilty) or No(I do not feel guilty) answers to answer every moral question that he could remember that had ever occurred in his life. In this way he could have become completely pure. He would have truly asked himself all the questions that could be asked of him. He would have emotionally evolved back to when he was a child.

What if he then assigned an ‘It doesn’t matter as life is only made to make mistakes’ label on every decision that he had analysed.

This would not make him God or the devil, but just very still and very exhausted. Anybody can do this but just for the purpose of this experiment lets say I have done this. Which I have.

There are no fears in me and if I died today I could deal with that because who can know me better than myself? Neither God or the Devil. I am consciously judging myself on ‘their’ level.

To make this work, despite my many faults, take ME as the ONLY universal constant. In this sense I have killed God and the Devil external to myself.The only place that they could exist is if I chose to believe they are internal.

This is obviously more a matter for a shrink more than a mathematician, but that would only be the case depending on what you believed the base operating system of the universe to be. Math / Physics / morals or some other concept.

As long I agreed to do NOTHING, to never move or think a thought, humanity would have something to peg all understanding on. Each person could send a moral choice and I would simply send back only one philosophy. ‘ LIFE IS ONLY FOR MAKING MISTAKES’.

People, for the purpose of this experiment could disbelief their belief system knowing they could go back to it at any time. It would give them an opportunity to unburden themselves to someone pure. A new Pandora’s box. Once everyone had finished I would simply format my drive and always leave adequate space for each individual to send any more thoughts that they thought were impure. People would then eventually end up with clear minds and have to be judged only on their physical efforts. Either good or bad. It would get rid of a lot of maybes which would speed lives along..

If we then assume that there are a finite(or at some point in the future, given a lot of hard work, there will be a finite amount) amount of topics that can be conceived of then we can realise that there will come to a time when we, as a people, will NOT have to work again.

Once we reach that point we will only have the option of doing the things we love or doing the things we hate as society will be completely catered for in every possible scenario. People will find their true path in life which will make them infinitely more happy, forever.

In this system there is no point in accounting for time in any context.

If we consider this to be The Grand Unified Theory then we can set the parameters as we please.

This will be our common goals for humanity. As before everyone would have their say. This could be a computer database that was completely updated in any given moment when a unique individual thought of a new idea / direction that may or may not have been thought before.

All that would be required is that every person on the planet have a mobile phone or access to the web and a self organising weighting algorithm biased on an initial set of parameters that someone has set to push the operation in a random direction.

As I’m speaking first I say we concentrate on GRAINE.

Genetics – Robotics – Artificial Intelligence – Nanotechnology and Zero Point Energy.

I have chosen these as I think the subjects will cross breed information(word of mouth first) at the present day optimum rate to get us to our finishing point, complete and finished mastery of all possible information.

Surely mastery of information in this way will lead us to the bottom of a fractal??? What if one end of the universes fractal was me??? What could we start to build with that concept???

As parameters, we can assume that we live only in 3 dimensions. We can place this box around The Milky Way galaxy as this gives us plenty of scope for all kinds of discoveries.

In this new system we can make time obsolete as it only making us contemplate our things that cannot be solved because up to now, no one has been willing to stand around for long enough. It has been holding us back.

All watches should be banned so that we find a natural rhythm with each other, those in our immediate area and then further afield.

An old clock watch in this system is should only be used when you think of an event that you need to go to. It is a compass, a modern day direction of thought.

A digital clock can be adapted to let you know where you are in relation to this new milky way boxed system.(x,y,z).

With these two types of clocks used in combination we can safely start taking small steps around the box by using the digital to see exactly where you are and then using the old watch to direct you as your thoughts come to you.

We can even build as many assign atomic clocks as are needed to individually track stars. Each and every star in the Milky Way galaxy.

I supposed a good idea would be to assume that I was inside the centre of the super-massive black hole at the centre of the galaxy. That would stop us from being so Earth centric.

We could even go as far as to say that we are each an individual star and that we project all our energies onto the super-massive black hole at the centre of the galaxy.

You can assume that I have stabilized the black hole into a non rotating perfect cube. 6 outputs /f aces in which we all see ‘the universe and earth, friends’ etc. This acts like a block hole mirror finish. Once you look it is very hard to look away from.

The 6 face cube should make the maths easier to run as you could construct the inner of the black hole with solid beams of condensed light(1 unit long) arranged into right angled triangles with set squares in for strength.

Some people would naturally say that if the universe is essentially unknowable as the more things we ‘discover’ the more things there are to combine with and therefore talk about. This is extremely fractal in both directions. There can be no true answers because there is no grounding point. Nothing for the people who are interested, to start building there own personal concepts, theories and designs on.

Is it possible that with just one man becoming conscious of a highly improbable possibility that all of universes fractals might collapse into one wave function that would answer all of humanities questions in a day? Could this be possible?

Answers to why we are here? What the point of life really is et al?

Is it possible that the insignificant possibility could become an escalating one that would at some point reach 100%???

Could it be at that point that the math would figure itself out so naturally that we would barely need to think about it. We would instantly understand Quantum theory and all.

Can anybody run the numbers on that probability?

11. April 14, 2015 5:51 pm

hi, there seems to be no ref to khot winning the nevanlinna prize 2014 for unique games conjecture on your blog anywhere which would be somewhat surprising if true.
BTW did you see this recent claim? credible? not credible? some comment by you or any experts at all would be helpful!
Refuting Unique Game Conjecture and d-to-1 Conjecture / Cui

• April 14, 2015 9:23 pm

You are right—we noted this, but wanted to have something new to say. Ironically, we are about to post about (one of) the winners of another prize. Thanks for the link—that may help, and we recognize some of this from previous contact with the author. Meanwhile I’ve been busy with this and other chess-cheating developments.