Rounding semidefinite programming hierarchies via global correlation

with , . 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.