Rounding Semidefinite Programming Hierarchies via Global Correlation

FOCS 2011, Fields institute, Barriers workshop in Princeton, SDP Day at CWI.

PDF

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

Joint work with Boaz Barak, and Prasad Raghavendra.