Computational Complexity

Monday, June 27, 2005

 
The Unique Games Conjecture

Posted by Lance

A unique game consists of an undirected connected graph G=(V,E), a color set C, and for each edge {i,j} with i<j a permutation π_i,j:C→C. A coloring of the graph c:V→C fulfills an edge {i,j} if π_i,j(c(i))=c(j).

There is also a linear version of unique games where C is a finite field and for each {i,j}, π_i,j(x)=a_i,jx+b_i,j with a_i,j and b_i,j in C and a_i,j≠0.

If a coloring fulfills all the edges then knowing the color at one edge uniquely determines all of the other colors. One can efficiently determine whether such a coloring exists by trying all possible colors at one node and seeing if any of the resulting coloring fulfills all the edges.

However it might be difficult to determine whether one can fulfill some large fraction of the edges. Subhash Khot defines the unique games conjecture.

For every constant δ>0 there is a fixed finite color class C such that it is NP-hard to distinguish the following two cases for any unique game with color class C.

1. There is some coloring that fulfills at least 1-δ-fraction of the edges.
2. Every coloring fulfills at most a δ-fraction of the edges.

Some results on unique games:

• Khot, Kindler, Mossel and O'Donnell reduce unique games to approximating Maximum Cut better than the best known approximation due to Goemans and Williamson (about 0.878567). Khot et. al. also required a "Majority is Stablest" conjecture which was later proved by Mossel, O'Donnell and Oleskiewicz. Thus under the unique games conjecture any improvement in approximating Max Cut would imply P=NP.
• Similar results showing that given the unique games conjecture (and P≠NP) it is hard to approximate Vertex Cover with 2-ε (Khot-Regev) and Sparsest Cut within any constant (Chalwa-Krauthgamer-Kumar-Rabani-Sivakumar).
• Luca Trevisan shows that we can solve the unique games in polynomial time if we allow δ=o(1/log n) instead of a constant.
• In an upcoming FOCS paper, Khot and Nisheeth Vishnoi use unique games to (unconditionally) disprove the conjecture that negative type metrics (metrics that are squares of Euclidean metrics) embed into L₁ with constant distortion. They also show a superconstant lower bound on the integrality ratio for Semi-Definite Programming relaxations for Sparsest Cut.

The introduction of Trevisan's paper gives a nice overview of unique games.

Update 6/28: The hardness of approximating sparsest cut given the unique game conjecture is also in the Khot-Vishnoi paper done independently from CKRRS. Also Khot has a recent survey in SIGACT News on PCP-based hardness results that has a section on unique games.

5:46 AM #

1.  Anonymous says:  
   
   Very nice and breif description of unique-game conjecture.
   

   11:41 AM, June 27, 2005

2.  Anonymous says:  
   
   Here is a meta-question: what other conjectures are out there that have been similarly applicable at simplifying a field? Are there similar conjectures that were eventually later proved to be true or false?
   
   -David Molnar
   

   5:43 PM, June 27, 2005

3.  Scott Aaronson says:  
   
   Well, one conjecture that similarly simplified a field was P!=NP.
   

   8:40 PM, June 27, 2005

4.  Luca says:  
   
   Another comparison, within the same sub-field, is with the assumption that "Max SNP is not contained in PTAS," that is, that Max 3SAT cannot be approximated arbitrarily well.
   
   Papadimitriou and Yannakakis defined Max SNP in the late 1980s, and showed that the approximability of several optimization problems depended on the resolution of this question. (That is, various problems had an approximation scheme if and only if all of Max SNP admited an approximation scheme, because said problems were proved to be complete for Max SNP under approximation-preserving reductions.)
   
   The PCP Theorem, of course, proved that indeed Max SNP is not contained in PTAS unless P=NP.
   
   With Unique Games, unfortunately, we do not yet have completeness results. That is, if the Unique Games conjecture is proved, then we have all these inapproximability results (modulo P =/= NP), but if the Unique Games conjecture is disproved, then we are left almost empty-handed. Notice the "almost": in any event the unconditional integrality gap results will survive, and so will the new results about the Fourier analysis of Boolean functions motivated by unique games.
   

   11:12 PM, June 27, 2005

5.  Anonymous says:  
   
   Well, the immportance of conjectures should not only be gauged by whether we can answer or not or even the number of implications it has. A big part of it is also the techniques and theory that get developed in an effort settle the conjecture. A good example would be FLT(Femat's Last Theorm). I don't know if the conjecture has any implication at all. However, algebraic number theory statred and developed in quest to settle it. And now when the cojecture is settled the field remains and we continue to discover interesting things.
   
   I completely agree with Scott. Not only it(P!=NP conjecture) has simplified the field, it has also had tremendous impact on our field.
   Much of complexity theory has been developed in quest of settling the P!=NP conjecture. Although we seem to be nowhere near to settle the conjecture but we atleast have settled some other questions. For instance, the work of Razborov in late 80s on monotone circuit lower bounds.
   
   Another good thing about Unique Games, which has also been pointed out by others, is that we have reduced optimal inapproximability results for many optimization problems to one question. Hence it becomes a "meta question" for the whole field. I think theory is all about that, isn't it?
   

   2:41 AM, June 28, 2005

6.  Anonymous says:  
   
   One could also argue that these conjectures arise organically while
   trying to solve problems. Hence
   they are part and parcel how
   research is done. On the other
   hand, we do need to pay attention
   to the chain of reductions as it
   gets longer.
   

   8:27 AM, June 28, 2005