Linear Level Lasserre Lower Bounds for Certain k-CSPs

We show that for k ≥ 3 even the Ω(n) level of the Lasserre hierarchy cannot disprove a random k-CSP instance over any predicate type implied by k-XOR constraints, for example k-SAT or k-XOR. (One constant is said to imply another if the latter is true whenever the former is. For example k-XOR constraints imply k-CNF constraints.) As a result the Ω(n) level Lasserre relaxation fails to approximate such CSPs better than the trivial, random algorithm. As corollaries, we obtain Ω(n) level integrality gaps for the Lasserre hierarchy of 76 − ε for Ver-texCover, 2 − ε for k-UniformHypergraphVertexCover, and any constant for k-UniformHypergraphIndependentSet. This is the first construction of a Lasserre inte-grality gap. Our construction is notable for its simplicity. It simplifies, strengthens, and helps to explain several previous results