There is also a linear version of unique games where C is a finite field and for each {i,j}, πi,j(x)=ai,jx+bi,j with ai,j and bi,j in C and ai,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.Some results on unique games:
- There is some coloring that fulfills at least 1-δ-fraction of the edges.
- Every coloring fulfills at most a δ-fraction of the edges.
- 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 L1 with constant distortion. They also show a superconstant lower bound on the integrality ratio for Semi-Definite Programming relaxations for Sparsest Cut.
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.
Very nice and breif description of unique-game conjecture.
ReplyDeleteHere 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?
ReplyDelete-David Molnar
Well, one conjecture that similarly simplified a field was P!=NP.
ReplyDeleteAnother 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.
ReplyDeletePapadimitriou 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.
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.
ReplyDeleteI 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?
One could also argue that these conjectures arise organically while
ReplyDeletetrying 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.
It is unnecessary to have i < j for permutation pi_{i, j}
ReplyDelete