The strongest approximation algorithms in literature employ linear
and semidefinite positive relaxations of integer programs.
“Sum of Squares” is a simple computation model that captures all
such techniques. We only know a handful of lower bounds for this
model, very few compared to more established (but weaker)
Lovász-Schrijver and Sherali-Adams hierarchies.
This course will focus on Sum of Squares: we will give an overview
of its relation with these earlier systems, 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.
TIMEFRAME: the course will consist in 16 lectures
of 2 hours each. It will start in Week 05 (period 3) and
will finish in Week 15 (period 4).
More information can be found at the course page.