×

zbMATH — the first resource for mathematics

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.)
PDF BibTeX XML Cite
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 · 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 · Zbl 1132.68418
[5] 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
[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 · 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 · 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
[14] S. Khot, O. Regev, Vertex cover might be hard to approximate to within \(2 - \operatorname{\&z.epsiv;}\), in: Proceedings of the 18th IEEE Annual Conference on Computational Complexity (CCC), 2003, pp. 379-386
[15] S. Khot, N. Vishnoi, The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into \(l_1\), in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, 2005, pp. 53-62
[16] Samorodnitsky, A.; Trevisan, L., A PCP characterization of NP with optimal amortized query complexity, (), 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.