Linear Level Lasserre Lower Bounds for Certain k-CSPs 论文

详细信息

发表日期

2008-10-01

发表年份

2008

摘要

We show that for kges3 even the Omega(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 Omega(n) level Lasserre relaxation fails to approximate such CSPs betterthan the trivial, random algorithm. As corollaries, we obtain Omega(n) level integrality gaps for the Lasserre hierarchy of 7/6-epsiv for VERTEXCOVER, 2-epsiv 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 simplifies, strengthens, and helps to explain several previous results.