Rounding semidefinite programming hierarchies via global correlation
with Boaz Barak, Prasad Raghavendra. FOCS 2011.
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).
- semidefinite programming
- constraint satisfaction problems
- strong relaxations