Rounding Semidefinite Programming Hierarchies via Global Correlation

Boaz Barak, Prasad Raghavendra, and David Steurer

October 2011

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)*.

Publication type | TechReport |

Number | MSR-TR-2011-107 |

Publisher | IEEE |

> Publications > Rounding Semidefinite Programming Hierarchies via Global Correlation