*Seminar Room, ground floor (Building IMAG)*

16 February 2017 - 11h00

High Degree Sum of Squares Proofs/Hierarchy for 0/1 Problems

by Mastrolilli Monaldo from IDSIA Lugano

Abstract: The Lasserre/Sum-of-Squares (SOS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems.

In this talk I will give a gentle introduction of the SOS framework for 0/1 problems from a more general point of view.

I will point it out that this more general definition is needed for certain class of problems e removes some of the weakness of the standard SOS approach.