Sums-of-squares integer programming relaxation: Lecture 5

by Massimo Lauria

Lecture 5: Properties of the Lasserre Relaxation.

Scribe: Sangxia Huang


In this lecture, we study the properties of the solution vectors of the Lasserre relaxation. We start with some basic properties of the solutions, and then continue to show that the solution vectors give us a family of locally consistent distributions over feasible integral local solutions. At the end of the lecture, we see an example of this property in graph coloring.

Link: [Lecture notes 05]