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