Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Rounding Semidefinite Programming Hierarchies via Global Correlation

Boaz Barak, Prasad Raghavendra, and David Steurer

Abstract

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 nO(r) constraints
specified by the rth level of the Lasserre hierarchy, and in
some cases r rounds of our program can be evaluated in time
2O(r)poly (n).

Details

Publication typeTechReport
NumberMSR-TR-2011-107
PublisherIEEE
> Publications > Rounding Semidefinite Programming Hierarchies via Global Correlation