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 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 .
2. Color red.
3. Select any vertex that is yet uncolored and is adjacent to a vertex that is colored. If 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 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 and 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 and a color .
2. Color with the color .
3. Select any vertex that is yet uncolored and is adjacent to a vertex that is colored. Use the edge rule to color . Note, there is no choice here once 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 . 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 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 so at least of the edges are satisfied;
• There is no assignment of colors to the vertices of so more than 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 there is an such that if some polynomial time algorithm distinguishes the above two situations for all unique-constraint graphs with 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 satisfiable instance of Unique Games on a -expander graph G with , finds a solution of cost

where and are some positive absolute constants.

Note, is the normalized edge expansion constant and is the smallest positive eigenvalue of the normalized Laplacian of the graph . 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

for . 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 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 be a -regular graph. Then, there is a trivial method to always find a solution to a UG problem with fraction of the edges satisfied. By Brook’s Theorem such a graph has a edge coloring: pick the most common color and these edges can be satisfied. Thus, if we are trying to separate a from fraction of the edges, the promise problem is meaningful only for .

Thus, if we are trying to separate from fraction of the edges, . The Makarychev and Makarychev’s theorem has a large constant , and

forces the degree to be very large. Unless I am wrong, if the graph is a spectral expander, then must be order and in any case it must be order .

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 . 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 versus 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.