TY - GEN

T1 - On the unique games conjecture

AU - Khot, Subhash

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2005

Y1 - 2005

N2 - The discovery of the PCP Theorem in 1992 led to an avalanche of hardness of approximation results, i.e. results showing that for certain NP-hard optimization problems, computing even approximate solutions is hard. However, for many fundamental problems, obtaining satisfactory hardness results seems out of reach of current techniques. The Unique Games Conjecture (UGC) was proposed in 2002 as an approach towards settling some of these open problems. A 2-Prover-1-Round game is called unique if for every answer of either prover, there is exactly one answer of the other prover if the verifier is to accept. The UGC states that for every constant ε > 0, it is NP-hard to distinguish whether the optimal strategy of provers in a unique 2P1R game has acceptance probability at least 1 - ε or at most ε. The answer size k = k(ε) could be an arbitrary function of ε. The UGC has been shown to imply optimal hardness results for Vertex Cover and MAX-CUT problems, and superconstant hardness results for Sparsest Cut and Min-2SAT-Deletion problems. A variation of the conjecture has been shown to imply hardness of coloring 3-colorable graphs with constantly many colors. Apart from these applications to hardness results, the UGC has led to important (unconditional) results in Fourier analysis, the theory of metric embeddings, and integrality gap results for semidefinite programming relaxations. The tutorial aims to give an overview of the UGC, its applications, and attempts to prove or disprove it. The powerpoint slides for the presentation are available at http://www.cc.gatech. edu/~khot.

AB - The discovery of the PCP Theorem in 1992 led to an avalanche of hardness of approximation results, i.e. results showing that for certain NP-hard optimization problems, computing even approximate solutions is hard. However, for many fundamental problems, obtaining satisfactory hardness results seems out of reach of current techniques. The Unique Games Conjecture (UGC) was proposed in 2002 as an approach towards settling some of these open problems. A 2-Prover-1-Round game is called unique if for every answer of either prover, there is exactly one answer of the other prover if the verifier is to accept. The UGC states that for every constant ε > 0, it is NP-hard to distinguish whether the optimal strategy of provers in a unique 2P1R game has acceptance probability at least 1 - ε or at most ε. The answer size k = k(ε) could be an arbitrary function of ε. The UGC has been shown to imply optimal hardness results for Vertex Cover and MAX-CUT problems, and superconstant hardness results for Sparsest Cut and Min-2SAT-Deletion problems. A variation of the conjecture has been shown to imply hardness of coloring 3-colorable graphs with constantly many colors. Apart from these applications to hardness results, the UGC has led to important (unconditional) results in Fourier analysis, the theory of metric embeddings, and integrality gap results for semidefinite programming relaxations. The tutorial aims to give an overview of the UGC, its applications, and attempts to prove or disprove it. The powerpoint slides for the presentation are available at http://www.cc.gatech. edu/~khot.

UR - http://www.scopus.com/inward/record.url?scp=33748627708&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748627708&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2005.61

DO - 10.1109/SFCS.2005.61

M3 - Conference contribution

AN - SCOPUS:33748627708

SN - 0769524680

SN - 9780769524689

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 3

BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

Y2 - 23 October 2005 through 25 October 2005

ER -