The Proofs to Algorithms Method in Algorithm Design
APA
(2025). The Proofs to Algorithms Method in Algorithm Design. SciVideos. https://youtube.com/live/RysGhdprrKs
MLA
The Proofs to Algorithms Method in Algorithm Design. SciVideos, May. 13, 2025, https://youtube.com/live/RysGhdprrKs
BibTex
@misc{ scivideos_ICTS:31837, doi = {}, url = {https://youtube.com/live/RysGhdprrKs}, author = {}, keywords = {}, language = {en}, title = {The Proofs to Algorithms Method in Algorithm Design}, publisher = {}, year = {2025}, month = {may}, note = {ICTS:31837 see, \url{https://scivideos.org/icts-tifr/31837}} }
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.