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].