%0 Conference Paper %1 khot02 %A Khot, Subhash %B Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing %C New York, NY, USA %D 2002 %I ACM %K complexity unique.game.conjecture %P 767--775 %R 10.1145/509907.510017 %T On the Power of Unique 2-prover 1-round Games %X A 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa (we implicitly assume games to be one round games). The value of a 2-prover game is the maximum acceptance probability of the verifier over all the prover strategies. We make the following conjecture regarding the power of unique 2-prover games, which we call the Unique Games Conjecture:(MATH) The Unique Games Conjecture: For arbitrarily small constants $ \ \zeta, \ > 0$, there exists a constant $k = k(\zeta,\delta)$ such that it is NP-hard to determine whether a unique 2-prover game with answers from a domain of size $k$ has value at least $1-\zeta$ or at most $\delta$. \medskip.(MATH) We show that a positive resolution of this conjecture would imply the following hardness results:<ol>For any $12 < t < 1$, for all sufficiently small constants $> 0$, it is NP-hard to distinguish between the instances of the problem 2-Linear-Equations mod 2 where either there exists an assignment that satisfies $1-\epsilon$ fraction of equations or no assignment can satisfy more than $1-\epsilon^t$ fraction of equations. As a corollary of the above result, it is NP-hard to approximate the Min-2CNF-deletion problem within any constant factor.For the constraint satisfaction problem where every constraint is the predicate Not-all-equal($a,b,c$), $ \ a, b, c GF(3) \ $, it is NP-hard to distinguish between the instances where either there exists an assignment that satisfies $1-\epsilon$ fraction of the constraints or no assignment satisfies more than $89+\epsilon$ fraction of the constraints for an arbitrarily small constant $> 0$. We also get a hardness result for a slight variation of approximate coloring of 3-uniform hypergraphs.</ol>.(MATH) We also show that a variation of the Unique Games Conjecture implies that for arbitrarily small constant $> 0$ it is hard to find an independent set of size $n$ in a graph that is guaranteed to have an independent set of size $Ømega(n)$.The main idea in all the above results is to use the 2-prover game given by the Unique Games Conjecture as an öuter verifier" and build new probabilistically checkable proof systems (PCPs) on top of it. The uniqueness property plays a crucial role in the analysis of these PCPs.(MATH) In light of such interesting consequences, we think it is an important open problem to prove (or disprove) the Unique Games Conjecture. We also present a semi-definite programming based algorithm for finding reasonable prover strategies for a unique 2-prover game. Given a unique 2-prover game with value $1-\zeta$ and answers from a domain of size $k$, this algorithm finds prover strategies that make the verifier accept with probability $1-O(k^2 \zeta^1/5 (\frac1\zeta))$. This result shows that the domain size $k = k(\zeta, \delta)$ must be sufficiently large if the Unique Games Conjecture is true. %@ 1-58113-495-9

@inproceedings{khot02, abstract = {A 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa (we implicitly assume games to be one round games). The value of a 2-prover game is the maximum acceptance probability of the verifier over all the prover strategies. We make the following conjecture regarding the power of unique 2-prover games, which we call the Unique Games Conjecture:(MATH) The Unique Games Conjecture: For arbitrarily small constants $ \ \zeta, \ \delta > 0$, there exists a constant $k = k(\zeta,\delta)$ such that it is NP-hard to determine whether a unique 2-prover game with answers from a domain of size $k$ has value at least $1-\zeta$ or at most $\delta$. \medskip.(MATH) We show that a positive resolution of this conjecture would imply the following hardness results:<ol>For any $\frac{1}{2} < t < 1$, for all sufficiently small constants $\epsilon > 0$, it is NP-hard to distinguish between the instances of the problem 2-Linear-Equations mod 2 where either there exists an assignment that satisfies $1-\epsilon$ fraction of equations or no assignment can satisfy more than $1-\epsilon^t$ fraction of equations. As a corollary of the above result, it is NP-hard to approximate the Min-2CNF-deletion problem within any constant factor.For the constraint satisfaction problem where every constraint is the predicate Not-all-equal($a,b,c$), $ \ a, b, c \in GF(3) \ $, it is NP-hard to distinguish between the instances where either there exists an assignment that satisfies $1-\epsilon$ fraction of the constraints or no assignment satisfies more than $\frac{8}{9}+\epsilon$ fraction of the constraints for an arbitrarily small constant $\epsilon > 0$. We also get a hardness result for a slight variation of approximate coloring of 3-uniform hypergraphs.</ol>.(MATH) We also show that a variation of the Unique Games Conjecture implies that for arbitrarily small constant $\delta > 0$ it is hard to find an independent set of size $\delta n$ in a graph that is guaranteed to have an independent set of size $\Omega(n)$.The main idea in all the above results is to use the 2-prover game given by the Unique Games Conjecture as an "outer verifier" and build new probabilistically checkable proof systems (PCPs) on top of it. The uniqueness property plays a crucial role in the analysis of these PCPs.(MATH) In light of such interesting consequences, we think it is an important open problem to prove (or disprove) the Unique Games Conjecture. We also present a semi-definite programming based algorithm for finding reasonable prover strategies for a unique 2-prover game. Given a unique 2-prover game with value $1-\zeta$ and answers from a domain of size $k$, this algorithm finds prover strategies that make the verifier accept with probability $1-O(k^2 \zeta^{1/5} \sqrt{\log (\frac{1}{\zeta})})$. This result shows that the domain size $k = k(\zeta, \delta)$ must be sufficiently large if the Unique Games Conjecture is true.}, acmid = {510017}, added-at = {2016-11-13T11:15:39.000+0100}, address = {New York, NY, USA}, author = {Khot, Subhash}, biburl = {https://www.bibsonomy.org/bibtex/2b3fcfe1e4b522e566341ed68ca771ef8/ytyoun}, booktitle = {Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing}, doi = {10.1145/509907.510017}, interhash = {082d0a18f2e9504da239f53dbded33d6}, intrahash = {b3fcfe1e4b522e566341ed68ca771ef8}, isbn = {1-58113-495-9}, keywords = {complexity unique.game.conjecture}, location = {Montreal, Quebec, Canada}, numpages = {9}, pages = {767--775}, publisher = {ACM}, series = {STOC '02}, timestamp = {2016-12-29T04:50:14.000+0100}, title = {On the Power of Unique 2-prover 1-round Games}, year = 2002 }