Unique Games: A Three Act Play
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 
- Pick any starting vertex
.
- Color
- Select any vertex
that is yet uncolored and is adjacent to a vertex that is colored. If
- Continue until all the vertices are colored.
- 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
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:
- Pick any starting vertex
.
- Color
- Select any vertex
- Continue until all the vertices are colored.
- If all the edge rules are satisfied the graph is satisfiable. If not go back to step (1) and try another color
. 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
- There exists an assignment of colors to the vertices of
of the edges are satisfied;
- There is no assignment of colors to the vertices of
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 
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
satisfiable instance of Unique Games on a
-expander graph G with
, finds a solution of cost
where
and
are some positive absolute constants.
Note, 
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
for 
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
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 
Thus, if we are trying to separate 
forces the degree 
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
Open Problems
What happens when we try to solve the UG problem on degree-3 graphs? What values of 
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.
Trackbacks
- Guessing the Truth « Gödel’s Lost Letter and P=NP
- FOCS 2010 accepted papers « Constraints
- Who Gets The Credit—Not Facebook Credits « Gödel’s Lost Letter and P=NP
- Coloring Graphs Made Easy? « Gödel’s Lost Letter and P=NP
- What’s Blue and White and Red All Over? « Gödel’s Lost Letter and P=NP
- Three Theorems About Growth | Gödel's Lost Letter and P=NP
- Lost in Complexity | Gödel's Lost Letter and P=NP
- Have Ten Years Brought Us Closer? | Gödel's Lost Letter and P=NP
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.
Instead of Brooks’ theorem you mean Vizing’s theorem:
http://mathworld.wolfram.com/VizingsTheorem.html
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?
Sorry. They were just names. Next time will use other colors.
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.
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.
Thanks for this quite useful comment.
Ryan, is n the number of vertices or the number of edges?
One question please. It seems that UGC would be false if e was constant rather than proportionnal to n. Is that right?
Unique Games is always satisfiable on a tree, so one can in fact trivially satisfy a fraction
of the constraints (where 
are the number of vertices and edges) in a d-regular graph.
Thanks. Can you do better?
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
I will have to do this. Very interesting question.
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?
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.
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?
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
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.
Hi why is the terminology ‘unique’ utilized?