Sum of squares and integer programming relaxations

For many optimization problems it  seems unfeasible to compute exact solutions, so there is a rich literature on algorithms for computing  approximate ones. Most such algorithms employ linear and semidefinite positive relaxations of integer programs.

 Sum of squares  (SOS) is a simple computational  model that captures essentially all known  such techniques. Despite being  the focus of
 intense research in the last decade, we only know a handful of lowe  bounds for  this model: very  few compared to more  established (but
 weaker) Lovász-Schrijver and Sherali-Adams hierarchies.

 In this course we will study the sums of squares model. We will give an overview of  the relation with these earlier  hierarchies, and we
 will see how  to use it to develop  better approximation algorithms. Then we will study its fundamental  limitations, in the form of rank
 lower bounds.

More information here