Special Colloquium
Subhabrata Sen
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