Talks
Fall 2017
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/opt7large-01.png?itok=MmjWP0n3)
Fast Spectral Algorithms from Sum-of-Squares Analyses
Thursday, November 9th, 2017, 12:00 pm–12:30 pm
Speaker:
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.