Unique games on expanding constraint graphs are easy: extended abstract

ABSTRACT

We present an efficient algorithm to find a good solution to the Unique Games problem when the constraint graph is an expander.

We introduce a new analysis of the standard SDP in this case that involves correlations among distant vertices. It also leads to a parallel repetition theorem for unique games when the graph is an expander.

REFERENCES

• 1: Christoph Ambuhl , Monaldo Mastrolilli , Ola Svensson, Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.329-337, October 21-23, 2007 [doi>10.1109/FOCS.2007.32]
• 2: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 3: Jin-yi Cai , Anne Condon , Richard J. Lipton, Playing Games of Incomplete Information, Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, p.58-69, February 22-24, 1990
• 4: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Near-optimal algorithms for unique games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132547]
• 5: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT, Computational Complexity, v.15 n.2, p.94-114, June 2006 [doi>10.1007/s00037-006-0210-9]
• 6: Eden Chlamtac , Konstantin Makarychev , Yury Makarychev, How to Play Unique Games Using Embeddings, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.687-696, October 21-24, 2006 [doi>10.1109/FOCS.2006.36]
• 7: Nikhil R. Devanur , Subhash A. Khot , Rishi Saket , Nisheeth K. Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132594]
• 8: Irit Dinur , Elchanan Mossel , Oded Regev, Conditional hardness for approximate coloring, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132567]
• 9: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 10: Anupam Gupta , Kunal Talwar, Approximating unique games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.99-106, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109569]
• 11: Thomas Holenstein, Parallel repetition: simplifications and the no-signaling case, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250852]
• 12: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 13: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 14: Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2--eps. In Proceedings of the Annual IEEE Conference on Computational Complexity, number 18, pages 379--386, 2003.
• 15: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 16: Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, v.11 n.3, p.796-817, 2000 [doi>10.1137/S1052623400366802]
• 17: Monique Laurent, A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0--1 Programming, Mathematics of Operations Research, v.28 n.3, p.470-496, July 2003 [doi>10.1287/moor.28.3.470.16391]
• 18: Laszlo Lovasz and Alexander Schrijver. Cones of matrices and set-functions and 0--1 optimization. SIAM Journal on Optimization, 1(2):166--190, 1991.
• 19: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 20: Anup Rao, Parallel repetition in projection games and a concentration bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374378]
• 21: Shmuel Safra and Oded Schwartz. On Parallel--Repetition, Unique-Game and Max-Cut. Manuscript, 2007.
• 22: Luca Trevisan, Approximation Algorithms for Unique Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.197-205, October 23-25, 2005 [doi>10.1109/SFCS.2005.22]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, expander graphs, semidefinite programming