Partitioning sparse random graphs: connections with mean-field spin glasses

Stochastics Seminar
Thursday, October 5, 2017 - 15:05
1 hour (actually 50 minutes)
Skiles 006
MIT / Microsoft
  The study of graph-partition problems such as Maxcut, max-bisection and min-bisection have a long and rich history in combinatorics and theoretical computer science. A recent line of work studies these problems on sparse random graphs, via a connection with mean field spin glasses. In this talk, we will look at this general direction, and derive sharp comparison inequalities between cut-sizes on sparse Erdös-Rényi and random regular graphs. Based on joint work with Aukosh Jagannath.