Rounding Semidefinite Programming Hierarchies via Global Correlation

Boaz Barak, Prasad Raghavendra, and David Steurer

October 2011

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

## Details

Publication type | TechReport |

Number | MSR-TR-2011-107 |

Publisher | IEEE |