Rounding Semidefinite Programming Hierarchies via Global Correlation

Understand

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 I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most \eps worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k\cdot\rank_{\geq \theta}(\Ins)/\poly(\e) \;, where k is the alphabet size of I, $\theta=\poly(\e/k)$, and $\rank_{\geq \theta}(\Ins)$ denotes the number of eigenvalues larger than $\theta$ in the normalized adjacency matrix of the constraint graph of $\Ins$.
• In the case that $\Ins$ is a \uniquegames instance, the threshold $\theta$ is only a polynomial in $\e$, and is independent of the alphabet size.