We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's).

More concretely, we show for every $2$-CSP instance $\Im$ a rounding algorithm for $r$ rounds of the Lasserre SDP hierarchy for $\Im$ that obtains an integral solution that is at most $\epsilon$ worse than the relaxation's value (normalized to lie in $[0,1]$), as long as
\[
r > k\cdot\mathrm{rank}_{\geq \theta}(\Im)/\poly(\epsilon) \;,
\]
where $k$ is the alphabet size of $\Im$, $\theta=\poly(\epsilon/k)$, and $\mathrm{rank}_{\geq \theta}(\Im)$ denotes the number of eigenvalues larger than $\theta$ in the normalized adjacency matrix of the constraint graph of $\Im$.

In the case that $\Im$ is a Unique Games instance, the threshold $\theta$ is only a polynomial in $\epsilon$, and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for every instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture.

Our algorithm actually requires less than the $n^{O(r)}$ constraints specified by the $r^{th}$ level of the Lasserre hierarchy, and in some cases $r$ rounds of our program can be evaluated in time $2^{O(r)}\mathrm{poly}(n)$.