Rounding Semidefinite Programming Hierarchies via Global Correlation
FOCS 2011, Fields institute, Barriers workshop in Princeton, SDP Day at CWI.
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.