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 in- put 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 3, a rounding algorithm for r rounds of the Lasserre SDP hierarchy for 3 that obtains an integral solution which is at most ε worse than the relaxation´s value (normalized to lie in [0, 1]), as long as r >; k·rank_≥θ(3)/ poly(ε), where k is the alphabet size of J, θ = poly(ε/k), and rank_≥θ(J) denotes the number of eigenvalues larger than θ in the normalized adjacency matrix of the constraint graph of J. In the case that J is a Unique Games instance, the threshold θ is only a polynomial in ε, 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 nol^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).