CSP gaps and reductions in the lasserre hierarchy

ABSTRACT

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck [23] recently showed the first integrality gaps for these problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as 2 even after Ω(n) rounds of the Lasserre hierarchy. We show that for the general MAX k-CSP problem, this ratio can be as large as 2^k/2k - ε when the alphabet is binary and q^k/q(q-1)k - ε when the alphabet size a prime q, even after Ω(n) rounds of the Lasserre hierarchy. We also explore how to translate gaps for CSP into integrality gaps for other problems using reductions, and establish SDP gaps for Maximum Independent Set, Approximate Graph Coloring, Chromatic Number and Minimum Vertex Cover. For Independent Set and Chromatic Number, we show integrality gaps of n/2^{O(√(log n log log n))} even after 2^{Ω(√(log n log log n))} rounds. In case of Approximate Graph Coloring, for every constant l, we construct graphs with chromatic number Ω(2^l/2/l²), which admit a vector l-coloring for the SDP obtained by Ω(n) rounds. For Vertex Cover, we show an integrality gap of 1.36 for Ω(n^δ) rounds, for a small constant δ. The results for CSPs provide the first examples of Ω(n) round integrality gaps matching hardness results known only under the Unique Games Conjecture. This and some additional properties of the integrality gap instance, allow for gaps for in case of Independent Set and Chromatic Number which are stronger than the NP-hardness results known even under the Unique Games Conjecture.

REFERENCES

• 1: Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060634]
• 2: Per Austrin , Elchanan Mossel, Approximation Resistant Predicates from Pairwise Independence, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.249-258, June 22-26, 2008 [doi>10.1109/CCC.2008.20]
• 3: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 4: Eli Ben-Sasson , Avi Wigderson, Short proofs are narrow—resolution made simple, Journal of the ACM (JACM), v.48 n.2, p.149-169, March 2001 [doi>10.1145/375827.375835]
• 5: Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
• 6: Moses Charikar , Konstantin Makarychev , Yury Makarychev, Near-optimal algorithms for maximum constraint satisfaction problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.62-68, January 07-09, 2007, New Orleans, Louisiana
• 7: Eden Chlamtac, Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.691-701, October 21-23, 2007 [doi>10.1109/FOCS.2007.13]
• 8: Eden Chlamtac , Gyanit Singh, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_5]
• 9: Irit Dinur and Shmuel Safra. On the hardness of approximating minimum vertex-cover. Annals of Mathematics, 162(1):439--486, 2005.
• 10: Lars Engebretsen and Jonas Holmerin. More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. In Proceedings of the 22th Symposium on Theoretical Aspects of Computer Science, pages 194--205, 2005.
• 11: U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
• 12: Uriel Feige. Randomized graph products, chromatic numbers, and the lovász vartheta-funktion. Combinatorica, 17(1):79--90, 1997.
• 13: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587]
• 14: Uriel Feige , Michael Langberg , Gideon Schechtman, Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers, SIAM Journal on Computing, v.33 n.6, p.1338-1368, 2004 [doi>10.1137/S0097539703431391]
• 15: Konstantinos Georgiou , Avner Magen , Toniann Pitassi , Iannis Tourlakis, Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.702-712, October 21-23, 2007 [doi>10.1109/FOCS.2007.34]
• 16: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 17: Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In ICALP (1), pages 226--237, 2006.
• 18: Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. In Proceedings of the 18th IEEE Conference on Computational Complexity, 2003.
• 19: Jean B. Lasserre, An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.293-303, June 13-15, 2001
• 20: 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]
• 21: L. Lovász and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM J. on Optimization, 1(12):166--190, 1991.
• 22: Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132519]
• 23: Grant Schoenebeck, Linear Level Lasserre Lower Bounds for Certain k-CSPs, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.593-602, October 25-28, 2008 [doi>10.1109/FOCS.2008.74]
• 24: Grant Schoenebeck , Luca Trevisan , Madhur Tulsiani, A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.205-216, June 13-March 16, 2007 [doi>10.1109/CCC.2007.2]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
constraint satisfaction, integrality gaps, semidefinite programming