David Steurer: Rounding Sum-of-Squares Relaxations

I will survey recent developments around the sum-of-squares method and its impact on computational complexity and algorithm design. In particular, we will discuss a general approach for showing guarantees of the sum-of-squares method based on a connection to the Positivstellensatz proof system.

This approach leads to improved algorithms for several problems arising in machine learning and optimization, in particular finding sparse vectors in subspaces, tensor optimization, and learning sparse dictionaries. Some of these problems are closely related to the Unique Games Conjecture and further quantitative improvements could refute the conjecture. Based on joint works with Boaz Barak and Jonathan Kelner.

The speaker was invited by Johan Håstad.