MIT / MSR New England
Random graphs, Optimization, and Spin glasses
Abstract: Combinatorial optimization problems are ubiquitous in diverse mathematical applications. The desire to understand their “typical” behavior motivates a study of these problems on random instances. In spite of a long and rich history, many natural questions in this domain are still intractable to rigorous mathematical analysis. Graph cut problems such as Max-Cut and Min-bisection are canonical examples in this class. On the other hand, physicists study these questions using the non-rigorous "replica" and "cavity" methods, and predict complex, intriguing features. In this talk, I will describe some recent progress in our understanding of their typical properties on random graphs, obtained via connections to the theory of mean-field spin glasses. The new techniques are broadly applicable, and lead to novel algorithmic and statistical consequences.
Colloquium tea to follow at 4pm in SEO 300.
Friday February 15, 2019 at 3:00 PM in 636 SEO