![Bridging Continuous and Discrete Optimization_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Bridging%20Continuous%20and%20Discrete%20Optimization_hi-res.png.jpg?itok=b7fmT0eV)
Abstract
The sum-of-squares hierarchy has led to new polynomial time algorithms for many problems, but solving semidefinite programs is often too computationally intensive to be practical. In this talk I'll describe a couple of works in which we bypass the use of constant-round SOS SDPs, and instead give lightweight (and sometimes near-linear time) spectral algorithms based on the SOS analyses.
Based on joint works with Sam Hopkins, Jonathan Shi and David Steurer.