Skip to main content
Browse by:

Until further notice, in-person public events have been canceled. Event listings include how to access online content.
Please check before coming to campus.

Random graphs, Optimization, and Spin glasses

Subhabrata Sen
Icon calendar
Monday, January 07, 2019
Icon time
12:00 pm - 1:00 pm
Icon speaker
Subhabrata Sen (MIT)
Icon series
Mathematics Colloquium Seminar

Combinatorial optimization problems are ubiquitous in diverse mathemati- cal 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.