Rounding semidefinite programming hierarchies via global correlation

with Boaz Barak, Prasad Raghavendra. FOCS 2011.

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

keywords

• semidefinite programming
• constraint satisfaction problems
• strong relaxations
• eigenvalues