The Proofs to Algorithms Method in Algorithm Design

Abstract

I will present a method developed roughly over the past decade and a half that reduces efficient algorithm design to finding "low-degree sum-of-squares" certificates -- thus proofs -- of uniqueness (or, more generally, "list uniqueness") of near-optimal solutions in input instances. This is a principled way of designing and analyzing a semidefinite programming relaxation + rounding algorithm for your target problem. This technique turns out be powerful tool in algorithm design. 

In this tutorial, I will introduce this technique and cover special cases of a couple of recent important applications. The first comes from a recent renaissance of efficient high-dimensional robust statistical estimation, where the proofs-to-algorithms method played a central role in the eventual resolution of the robust Gaussian Mixture learning problem (dating back to Pearson in 1894 and a concrete version due to Vempala in 2010). The second will be drawn from combinatorial optimization. It will focus on finding planted cliques in the semirandom model, answering a question dating back to Feige and Kilian (2001) and, more recently, by Feige (2019) and Steinhardt (2018). 

Both applications are glimpses of a rich research area in which young researchers may find interesting directions for further research.