Computer Science Theory Seminar
Chris Jones
University of Chicago
Lower bounds against the sum-of-squares algorithm
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.
Wednesday November 10, 2021 at 3:00 PM in 636 SEO