On Some Easy Problems That Are Hard for the Lasserre Hierarchy

On Some Easy Problems That Are Hard for the Lasserre Hierarchy

Explore a 28-minute lecture on the Lasserre hierarchy and its limitations in solving certain optimization problems. Gain insights into lower bound results for this hierarchy, including characterizations of problems with integrality gaps at high levels. Learn about a scheduling problem solvable in O(n log n) time that exhibits an unbounded integrality gap in the Lasserre hierarchy. Discover how symmetry in problem formulations can simplify the analysis of positive semidefiniteness. Examine a concise proof of the Grigoriev/Laurent lower bound for the integer cut polytope of complete graphs. This talk, presented by Monaldo Mastrolilli at the Hausdorff Center for Mathematics, covers joint work with A. Kurpisz and S. Leppanem.