Abstract
A common theme in several recent works is that proofs in restricted proof systems like sum-of-squares, can inform the design of efficient algorithms, especially for the kind of estimation problems that arise in statistics and machine learning.
To illustrate this theme, we discuss the examples of tensor completion, dictionary learning, and community detection.
Based on joint works with Boaz Barak, Sam Hopkins, Jon Kelner, Tengyu Ma, Aaron Potechin, Tselil Schramm, Jonathan Shi.