Rounding Semidefinite Programming Hierarchies via Global Correlation

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 Ins a rounding algorithm for r rounds of the Lasserre SDP hierarchy for Ins that obtains an integral solution that is at most e worse than the relaxation’s value (normalized to lie in [0,1]), as long as r > k·rank_{≥ θ}(Ins )/poly (e ) \;, where k is the alphabet size of Ins , θ=poly (e /k), and rank_{≥ θ}(Ins ) denotes the number of eigenvalues larger than θ in the normalized adjacency matrix of the constraint graph of Ins .

In the case that Ins is a uniquegames instance, the threshold θ is only a polynomial in e , 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)poly (n).