Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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 Unique Games. Our algorithm matches the performance of the recent algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst-case, but is shown to run in polynomial time on a richer family of instances, thus ruling out more possibilities for hard instances for the Unique Games Conjecture. Specifically, we give a rounding algorithm for $O(r)$ levels of the Lasserre hierarchy that finds a good integral solution as long as, very roughly speaking, the average correlation between vectors in the SDP solution is at least $1/r$. In the case of Unique Games, the latter condition is implied by having at most $r$ large eigenvalues in the constraint graph. This improves upon prior works that required the potentially stronger condition of a bound on the number of eigenvalues in the \emph{label extended graph}. Our algorithm actually requires less than the $n^{O(r)}$ constraints specified by the $r^{th}$ level of the Lasserre hierarchy, and in particular $r$ rounds of our program can be evaluated in time $2^{O(r)}\mathrm{poly}(n)$.

Questions and Answers

You need to be logged in to be able to post here.