IMT, Toulouse

November 6-8 2019

• David Steurer (ETH Zurich). Mini Course.

We study a class of estimation problems that captures a wide-range of interesting questions from various discplinies, including tensor decomposition, matrix and tensor completion, planted clique, community detection, clustering, and robust mean estimation. For many of these problems, the guarantees we know for computationally efficient methods are significantly worse than those of methods that may take exponential time in the size of the input. This situation raises the question if we can find computationally efficient methods with better guarantees or if the gap is inherent. In this course, we discuss a meta algorithm for estimation problems based on the sum-of-squares method. For many important estimation problems, this algorithm achieves substantially better guarantees than previous methods and it is plausible that those guarantees are best possible.