Mathematics Colloquium Seminar
Monday, January 7, 2019, 12:00pm, 119 Physics
Subhabrata Sen (MIT)
Random graphs, Optimization, and Spin glasses

Abstract:

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. [video]

---

Generated at 4:04pm Friday, April 19, 2024 by Mcal.   Top * Reload * Login