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

@inproceedings{Khot2002OnTP, title={On the power of unique 2-prover 1-round games}, author={Subhash Khot}, booktitle={STOC '02}, year={2002} }

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… Expand

#### Topics from this paper

#### 489 Citations

A note on Unique Games

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2006

A tighter analysis of the algorithm of Khot shows that given a unique 2-prover-1-round game with value 1 - e, one can find in polynomial time an assignment to the game with an expected weight of 1 - O(k6/5e1/5 (log 1/ek)2/5), where k is the size of the answer domain. Expand

Parallel Repetition of Two-Prover One-Round Games: An Exposition

- Mathematics
- 2015

A two-prover one-round game is a fundamental combinatorial optimization problem arising from such areas as interactive proof systems, hardness of approximation, cryptography and quantum mechanics.… Expand

Unique Games with Entangled Provers are Easy

- Mathematics, Physics
- 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- 2008

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e.,… Expand

Unique Games with Entangled Provers are Easy

- Mathematics, Computer Science
- FOCS
- 2008

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e.,… Expand

On the complexity of unique games and graph expansion

- Mathematics
- 2010

Understanding the complexity of approximating basic optimization problems is one of the grand challenges of theoretical computer science. In recent years, a sequence of works established that Khot’s… Expand

On the power of many one-bit provers

- Mathematics, Computer Science
- ITCS '13
- 2013

It is demonstrated that for the case that k ≥ 2, 1-bit k-prover games exhibit a significantly richer structure and yield a natural "quantitative" approach to relating complexity classes such as BPP, SZK, AM, EXP, and NEXP. Expand

Refuting Unique Game Conjecture and d-to-1 Conjecture

- Mathematics
- 2015

In this paper, the author proves a weighted k-CSP with the support of its predicate the ground of a balanced pairwise independent distribution is approximation resistant under weak form of d-to-1… Expand

NP-Hardness of Approximately Solving Linear Equations over Reals

- Computer Science, Mathematics
- SIAM J. Comput.
- 2010

This paper considers the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables and develops linearity and dictatorship testing procedures for functions $f: \mathbb{R}^n \mapsto Â£R}$ over a Gaussian space, which could be of independent interest. Expand

The Parallel Repetition Theorem and Related Results

- 2010

In a 2-Prover 1-Round Game, a verifier draws a pair of questions (X,Y ) from a distribution D and sends one each to two co-operating, non-communicating players who need to respond back with answers… Expand

A Counterexample to Strong Parallel Repetition

- Mathematics, Computer Science
- FOCS
- 2008

A major motivation for the recent interest in the strong parallel repetition problem is that a strong Parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least 1 - isin2 satisfiable from instances that areat most 1 - (2/pi) ldr isin satisfiable. Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

Two-prover one-round proof systems: their power and their problems (extended abstract)

- Mathematics, Computer Science
- STOC '92
- 1992

This work characterize the power of two-prover one-round MIP proof systems, and proves the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs. Expand

Hardness of approximate hypergraph coloring

- Computer Science, Mathematics
- Electron. Colloquium Comput. Complex.
- 2000

It is proved that, for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors and also yields a superconstant inapproximability result under a stronger hardness assumption. Expand

A parallel repetition theorem

- Mathematics, Computer Science
- STOC '95
- 1995

We show that a parallel repetition of any two-prover one-round proof system (MIP(2; 1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The… Expand

Free bits, PCPs and non-approximability-towards tight results

- Computer Science, Mathematics
- Proceedings of IEEE 36th Annual Foundations of Computer Science
- 1995

A proof system for NP is presented using logarithmic randomness and two amortized free bits, so that Max clique is hard within N/sup 1/3/ and chromatic number within N-Sup 1/5/, and a comprehensive study of PCP and FPCP parameters is initiated. Expand

Proof verification and hardness of approximation problems

- Computer Science, Mathematics
- Proceedings., 33rd Annual Symposium on Foundations of Computer Science
- 1992

The authors improve on their result by showing that NP=PCP(logn, 1), which has the following consequences: (1) MAXSNP-hard problems do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup ePSilon / unless P =NP. Expand

A PCP characterization of NP with optimal amortized query complexity

- Mathematics, Computer Science
- STOC '00
- 2000

It is shown that k-CSP, the problem of finding an assignment satisfying the maximum number of given constraints (where each constraint involves at most k variables) is NP-hard to approximate to within a factor 2 √ . Expand

On the distribution of the fourier spectrum of Boolean functions

- Mathematics
- 2002

AbstractIn this paper we obtain a general lower bound for the tail distribution of the Fourier spectrum of Boolean functionsf on {1, −1}N. Roughly speaking, fixingk∈ℤ+ and assuming thatf is not… Expand

Probabilistic checking of proofs: a new characterization of NP

- Mathematics, Computer Science
- JACM
- 1998

It is shown that approximating Clique and Independent Set, even in a very weak sense, is NP-hard, and the class NP contains exactly those languages for which membership proofs can be verified probabilistically in polynomial time. Expand

Finding almost-satisfying assignments

- Mathematics, Computer Science
- STOC '98
- 1998

It is shown that ZSAT and HORN-SAT are, essentially, the only non-trivial classes of formulae for which almost-satisfying assignments can be found in polynomial time (assuming P # NP). Expand

Approximating the independence number via theϑ-function

- Mathematics, Computer Science
- Math. Program.
- 1998

An approximation algorithm for the independence number of a graph that improves the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size Ω(m1/(k−1)) in such a graph. Expand