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]