Abstract

I will present a new method for proving sum-of-squares lower bounds, applied in particular to problems over the hypercube such as Max-Cut and optimizing the Sherrington-Kirkpatrick (SK) Hamiltonian, where we expect these powerful algorithms to do no better than a simple spectral bound. The method builds certificates that are positive-semidefinite by construction, thereby easing some of the difficulties common to other methods, such as pseudocalibration. I will discuss the lower bounds of small degree this achieves for the SK Hamiltonian, some intrinsic limitations, and what would be required for higher-degree lower bounds.

Time permitting, I will also mention how this approach brings forward some of the mathematical facts behind why sum-of-squares certificates can satisfy both the entrywise and spectral constraints required of them. Over the hypercube, it suggests that the responsible phenomenon is an intriguing combinatorial relationship between multiharmonic polynomials, partitions, and the Mobius function of a partially ordered set of forests.

Attachment

Video Recording