On the power of unique 2-prover 1-round games

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.

REFERENCES

• 1: N. Alon and N. Kahale. Approximating the independence number via the θ-function. Technical Report, Tel Aviv University, 1995.
• 2: Gunnar Andersson , Lars Engebretsen , Johan Håstad, A new way of using semidefinite programming with applications to linear equations mod p, Journal of Algorithms, v.39 n.2, p.162-204, May 2001 [doi>10.1006/jagm.2000.1154]
• 3: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 4: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 5: M. Bellare, O. Goldreich, and M. Sudan. Free bits, pcps and non-approximability. Electronic Colloquium on Computational Complexity, Technical Report TR95-024, 1995.
• 6: J. Bourgain. On the distribution of the fourier spectrum of boolean functions. manuscript.
• 7: Irit Dinur , Shmuel Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509915]
• 8: U. Feige, Error reduction by parallel repetition-the state of the art, Weizmann Science Press of Israel, Jerusalem, Israel, 1995
• 9: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 10: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 11: A. Frieze and M. Jerrum. Improved approximation algorithms for max k-cut and max bisection. Algorihmica, 18:67--81, 1997.
• 12: Michel X. Goemans , David P. Williamson, .879-approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.422-431, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195216]
• 13: V. Guruswami , J. Hastad , M. Sudan, Hardness of approximate hypergraph coloring, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.149, November 12-14, 2000
• 14: J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
• 15: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 16: J. Håstad. On a protocol possibly useful for min-2sat. unpublished manuscript.
• 17: V. Kann, S. Khanna, J. Lagergren, and A. Panconesi. On the hardness of max k-cut and its dual. In Proc. of the 5th Israel Symposium on Theory and Computing Systems, pages 61--67, 1996.
• 18: Subhash Khot, Hardness results for approximate hypergraph coloring, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509962]
• 19: Philip N. Klein , Serge A. Plotkin , Satish Rao , Éva Tardos, Approximation algorithms for Steiner and directed multicuts, Journal of Algorithms, v.22 n.2, p.241-269, Feb. 1997 [doi>10.1006/jagm.1996.0833]
• 20: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 21: Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
• 22: Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States
• 23: Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276869]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

General Terms:
Algorithms, Experimentation, Performance, Theory