##
**A note on unique games.**
*(English)*
Zbl 1185.91017

Summary: We give a tighter analysis of the algorithm of S. Khot [“On the power of unique 2-prover 1-round games”, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 767–775 (2002)] which shows that given a unique 2-prover-1-round game with value \(1 - \varepsilon \), one can find in polynomial time an assignment to the game with an expected weight of \(1 - O(k^{6/5} \varepsilon ^{1/5} (\log \frac {1}{\varepsilon k})^{2/5})\), where \(k\) is the size of the answer domain. This shows that if the unique games conjecture is true then the domain size \(k\), must be at least \(\Omega ((\varepsilon ^{1/6}\log ^{1/3}(1/\varepsilon ))^{ - 1})\), which is an improvement over the previous \(\Omega ((\varepsilon ^{1/10}\log ^{1/4}(1/\varepsilon ))^{ - 1})\) bound.

### MSC:

91A05 | 2-person games |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

### Keywords:

algorithms; analysis of algorithms; approximation algorithms; computational complexity; theory of computation
PDFBibTeX
XMLCite

\textit{A. Avidor} and \textit{R. Rosen}, Inf. Process. Lett. 99, No. 3, 87--91 (2006; Zbl 1185.91017)

Full Text:
DOI

### References:

[1] | Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and the hardness of approximation problems, Journal of the ACM, 45, 501-555 (1998) · Zbl 1065.68570 |

[2] | S. Arora, M. Safra, Probabilistic checking of proofs: a new characterization of NP, in: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 2-13; S. Arora, M. Safra, Probabilistic checking of proofs: a new characterization of NP, in: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992, pp. 2-13 · Zbl 0945.68516 |

[3] | Bellare, M.; Goldreich, O.; Sudan, M., Free bits, PCPs, and nonapproximability—towards tight results, SIAM Journal on Computing, 27, 3, 804-915 (1998), (electronic) · Zbl 0912.68041 |

[4] | S. Chawla, R. Krauthgamer, Y. Rabani, D. Sivakumar, On the hardness of approximating multicut and sparsest-cut, in: IEEE Conference on Computational Complexity, 2005, pp. 144-153; S. Chawla, R. Krauthgamer, Y. Rabani, D. Sivakumar, On the hardness of approximating multicut and sparsest-cut, in: IEEE Conference on Computational Complexity, 2005, pp. 144-153 · Zbl 1132.68418 |

[5] | I. Dinur, E. Mossel, O. Regev, Conditional hardness for approximate coloring, ECCC Technical Report TR05-039, 2005; I. Dinur, E. Mossel, O. Regev, Conditional hardness for approximate coloring, ECCC Technical Report TR05-039, 2005 · Zbl 1301.68143 |

[6] | U. Feige, L. Lovász, Two-prover one-round proof systems: Their power and their problems (extended abstract), in: Proceedings of the 24rd Annual ACM Symposium on Theory of Computing, Victoria, Canada, 1992, pp. 733-744; U. Feige, L. Lovász, Two-prover one-round proof systems: Their power and their problems (extended abstract), in: Proceedings of the 24rd Annual ACM Symposium on Theory of Computing, Victoria, Canada, 1992, pp. 733-744 |

[7] | U. Feige, D. Reichman, On systems of linear equations with two variables per equation, in: 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 8th International Workshop on Randomization and Computation, Boston, MA, 2004, pp. 117-127; U. Feige, D. Reichman, On systems of linear equations with two variables per equation, in: 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 8th International Workshop on Randomization and Computation, Boston, MA, 2004, pp. 117-127 · Zbl 1105.68047 |

[8] | Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 1115-1145 (1995) · Zbl 0885.68088 |

[9] | Guruswami, V.; Håstad, J.; Sudan, M., Hardness of approximate hypergraph coloring, SIAM Journal on Computing, 31, 6, 1663-1686 (2002), (electronic) · Zbl 1008.68052 |

[10] | Håstad, J., Clique is hard to approximate within \(n^{1 - \operatorname{\&z.epsiv;}} \), Acta Mathematica, 182, 1, 105-142 (1999) · Zbl 0989.68060 |

[11] | Håstad, J., Some optimal inapproximability results, Journal of the ACM, 48, 4, 798-859 (2001), (electronic) · Zbl 1127.68405 |

[12] | S. Khot, On the power of unique 2-prover 1-round games, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 2002, pp. 767-775; S. Khot, On the power of unique 2-prover 1-round games, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Quebec, Canada, 2002, pp. 767-775 · Zbl 1192.68367 |

[13] | S. Khot, G. Kindler, E. Mossel, R. O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, in: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 146-154; S. Khot, G. Kindler, E. Mossel, R. O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, in: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 146-154 |

[14] | S. Khot, O. Regev, Vertex cover might be hard to approximate to within \(2 -; \operatorname{\\(\#\#\#\#\\)} \); S. Khot, O. Regev, Vertex cover might be hard to approximate to within \(2 -; \operatorname{\\(\#\#\#\#\\)} \) |

[15] | S. Khot, N. Vishnoi, The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into \(l_1\); S. Khot, N. Vishnoi, The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into \(l_1\) |

[16] | Samorodnitsky, A.; Trevisan, L., A PCP characterization of NP with optimal amortized query complexity, (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (2000), ACM: ACM New York), 191-199, (electronic) · Zbl 1296.68060 |

[17] | L. Trevisan, Approximation algorithms for unique games, in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 2005, pp. 197-205; L. Trevisan, Approximation algorithms for unique games, in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 2005, pp. 197-205 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.