Approximation Algorithms for Unique Games

by Luca Trevisan

Theory of Computing, Volume 4(5), pp. 111-128, 2008

Bibliography with links to cited articles

[1] Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth Vishnoi: Unique games on expanding constraint graphs are easy. In Proc. 40th STOC, pp. 21-28. ACM Press, 2008. [STOC:10.1145/1374376.1374380].
[2] Per Austrin: Balanced max 2-SAT might not be the hardest. In Proc. 39th STOC, pp. 189-197. ACM Press, 2007. [STOC:10.1145/1250790.1250818].
[3] Per Austrin: Towards sharp inapproximability for any 2-CSP. In Proc. 48th FOCS, pp. 307-317. IEEE Computer Society, 2007. [FOCS:10.1109/FOCS.2007.73].
[4] Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Near-optimal algorithms for unique games. In Proc. 38th STOC, pp. 205-214. ACM Press, 2006. [STOC:1132516.1132547].
[5] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D.Sivakumar: On the hardness of approximating multicut and sparsest-cut. In Proc. 20th IEEE Conf. on Computational Complexity, pp. 144-153. IEEE Computer Society, 2005. [CCC:10.1109/CCC.2005.20].
[6] Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev: How to play unique games using embeddings. In Proc. 47th FOCS, pp. 687-696. IEEE Computer Society, 2006. [FOCS:10.1109/FOCS.2006.36].
[7] Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. In Proc. 38th STOC, pp. 344-353. ACM Press, 2006. [STOC:1132516.1132567].
[8] Uri Feige and László Lovász: Two-prover one round proof systems: Their power and their problems. In Proc. 24th STOC, pp. 733-741. ACM Press, 1992. [STOC:129712.129783].
[9] Uriel Feige and Daniel Reichman: On systems of linear equations with two variables per equation. In 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'04), pp. 117-127. Springer, 2004. [Springer:uk7fpuul45c5h6j5].
[10] Anupam Gupta and Kunal Talwar: Approximating unique games. In Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA'06), pp. 99-106. ACM Press, 2006. [SODA:1109557.1109569].
[11] Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767-775. ACM Press, 2002. [STOC:509907.510017].
[12] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell: Optimal inapproximability results for MAX-CUT and other two-variable CSPs? In Proc. 45th FOCS, pp. 146-154. IEEE Computer Society, 2004. [FOCS:10.1109/FOCS.2004.49].
[13] Subhash Khot and Ryan O'Donnell: SDP gaps and UGC-hardness for MAXCUTGAIN. In Proc. 47th FOCS, pp. 217-226. IEEE Computer Society, 2006. [FOCS:10.1109/FOCS.2006.67].
[14] Subhash Khot and Oded Regev: Vertex cover might be hard to approximate to within 2-ε. J. Comput. System Sci., 74:335-349, 2008. Preliminary version in Proc. CCC'03. [JCSS:10.1016/j.jcss.2007.06.019].
[15] Subhash Khot and Nisheeth Vishnoi: The unique games conjecture, integrality gap for cut problems and the embeddability of negative type metrics into 1. In Proc. 46th FOCS, pp. 53-63. IEEE Computer Society, 2005. [FOCS:10.1109/SFCS.2005.74].
[16] Frank T. Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46:787-832, 1999. [JACM:331524.331526].
[17] Rajeskar Manokaran, Seffi Naor, Prasad Raghavendra, and Roy Schwartz: SDP gaps and UGC hardness for multiway cut, 0-extension and metric labeling. In Proc. 40th STOC, pp. 11-20. ACM Press, 2008. [STOC:10.1145/1374376.1374379].
[18] Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. In Proc. 46th FOCS, pp. 21-30. IEEE Computer Society, 2005. [FOCS:10.1109/SFCS.2005.53].
[19] Kenji Obata: Approximate max-integral-flow/min-multicut theorems. In Proc. 36th STOC, pp. 539-545. ACM Press, 2004. [STOC:1007352.1007433].
[20] Ryan O'Donnell and Yi Wu: An optimal SDP algorithm for Max-Cut, and equally optimal long code tests. In Proc. 40th STOC, pp. 335-344. ACM Press, 2008. [STOC:10.1145/1374376.1374425].
[21] Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245-254. ACM Press, 2008. [STOC:10.1145/1374376.1374414].
[22] Ran Raz: A parallel repetition theorem. SIAM J. Computing, 27(3):763-803, 1998. Preliminary version in STOC'95. [SICOMP:10.1137/S0097539795280895, STOC:225058.225181].
[23] Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. In Proc. 38th STOC, pp. 11-20. ACM Press, 2006. [STOC:10.1145/1132516.1132519].

This file has been generated by bibtex2html 1.85.