Boaz Barak, Prasad Raghavendra, and David Steurer
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
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