Paper Info
Title
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 2k/2k - ε when the alphabet is binary and qk/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/2O(√(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 Ω(2l/2/l2), 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.
Year
DOI
Venue
2009
10.1145/1536414.1536457
Electronic Colloquium on Computational Complexity
Keywords
Field
DocType
lasserre hierarchy,constraint satisfaction,semidefinite programming,integrality gap,independent set,integrality gap instance,unique games conjecture,round integrality,approximate graph coloring,chromatic number,sdp gap,integrality gaps,n log log n,csp gap,graph coloring,maximum independent set,constraint satisfaction problem,vertex cover
Integer,Prime (order theory),Binary logarithm,Discrete mathematics,Combinatorics,Unique games conjecture,Independent set,Vertex cover,Semidefinite programming,Mathematics,Graph coloring
Conference
Volume
Issue
ISSN
15
104
0737-8017
Citations 
PageRank 
References 
70
1.86
24
Authors
1
Name
Order
Citations
PageRank
Madhur Tulsiani135824.60