Abstract

Algorithms based on the sum-of-squares hierarchy have greatly extended the class of tensors for which we have polynomial-time algorithms with provable guarantees. However, 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.