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 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\cdot\rank_{\geq \theta}(\Ins)/\poly(\e) \;,

\]

where $k$ is the alphabet size of $\Ins$, $\theta=\poly(\e/k)$,

and $\rank_{\geq \theta}(\Ins)$ denotes the number of eigenvalues

larger than $\theta$ in the normalized adjacency matrix of the constraint graph of $\Ins$.

In the case that $\Ins$ is a \uniquegames instance, the threshold $\theta$ 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

\emph{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)$.

SDP-hierarchies.pdf
PDF file

Publisher  IEEE

Details

TypeTechReport
NumberMSR-TR-2011-107
> Publications > Rounding Semidefinite Programming Hierarchies via Global Correlation