Chris Jones : Lower bounds against the sum-of-squares algorithm

Posted by Karoline Dubin , part of the Computer Science Theory Seminar.

At

Nov. 10, 2021, 3 p.m.

In

636 SEO

Abstract

The sum-of-squares algorithm is a powerful combinatorial optimization algorithm that can be run as a black box on a given problem. However, it is currently quite difficult to determine whether or not sum-of-squares solves the problem, since sum-of-squares is too slow to run in practice, and theoretical analysis is difficult. I will discuss two recent works on lower bounds against sum-of-squares on specific problems: first, for the problem of minimizing the Sherrington-Kirkpatrick Hamiltonian, and second, for the Independent Set problem on sparse graphs. The lower bounds utilize matrix-valued Fourier analysis, combining both combinatorial and spectral techniques.