Departmental Colloquium
Will Perkins
University of Birmingham
Randomized computational problems and the cavity method
Abstract: Random instances of computational problems play an important role in computer science as a source of hard instances, a testbed for algorithms, and as practical constructions of error correcting codes. The biggest breakthrough in our understanding of these problems in the last decade has come from statistical physicists who were originally interested in the properties of glasses. Their intricate but non-rigorous "cavity method” gives a series of detailed predictions of the behavior of randomized computational problems.
I will describe a mathematical vindication of the cavity method in a broad class of models. Using a mix of tools, new and old, we make rigorous the calculations the physicists have been doing all along. Some consequences of our results include determining the information theoretic threshold in the disassortative stochastic block model and the condensation threshold in the random graph coloring problem. Based in part on joint work with A. Coja-Oghlan, F. Krzakala, and L. Zdeborova.
There will be tea at 4pm, after the talk
Thursday January 18, 2018 at 3:00 PM in SEO 636