Sums-of-squares integer programming relaxation: Lecture 6
by Massimo Lauria
Lecture 6: Max-Cut approximation as a Lasserre rounding.
Scribe: Marc Vinyals
We show how to give a good approximation for the max-cut problem using only low levels of the Lasserre hierarchy. This implies a separation between Sherali-Adams and Lasserre hierarchies. Additionally we introduce basic Fourier analysis in the boolean setting.
Link: [Lecture notes 06]