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 7⁄6 - ε for VertexCover, 2-ε for k-UniformHypergraphVertexCover, and any constant for k-UniformHypergraphIndependentSet. This is the first construction of a Lasserre integrality gap.
Our construction is notable for its simplicity. It simplifes, strengthens, and helps to explain several previous results.