# Subhabrata Sen : Random graphs, Optimization, and Spin glasses

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.

**Category**: Colloquium**Duration**: 01:34:58**Date**: January 7, 2019 at 11:55 AM**Views**: 176-
**Tags:**seminar, Mathematics Colloquium Seminar

## 0 Comments