We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck 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 $\Omega(n)$ rounds of the Lasserre hierarchy.

We show that for the general \kcsp ~problem over binary domain, the ratio of SDP optimum to the value achieved by the optimal assignment, can be as large as $2^k/2k - \epsilon$ even after $\Omega(n)$ rounds of the Lasserre hierarchy. For alphabet size $q$ which is a prime, we give a lower bound of $q^k/q(q-1)k - \epsilon$ for $\Omega(n)$ rounds. The method of proof also gives optimal integrality gaps for a predicate chosen at random.

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(\sqrt{\log n \log\log n})}$ even after $2^{\Omega(\sqrt{\log n \log \log n})}$ rounds. In case of Approximate Graph Coloring, for every constant $l$, we construct graphs with chromatic number $\Omega(2^{l/2}/l^2)$, which admit a vector $l$-coloring for the SDP obtained by $\Omega(n)$ rounds. For Vertex Cover, we show an integrality gap of 1.36 for $\Omega(n^{\delta})$ rounds, for a small constant $\delta$.

The results for CSPs provide the first examples of $\Omega(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.