Stochastic block models and probabilistic reductions

Stochastic block models and probabilistic reductions - Emmanuel Abbe

Emmanuel Abbe
Princeton University
November 28, 2016
The stochastic block model (SBM) is a random graph model with planted clusters. It has been popular to model unsupervised learning problems, inhomogeneous random graphs and to study statistical versus computational tradeoffs. This talk overviews the recent developments that establish the thresholds for SBMs, the algorithms that achieve the thresholds, and the techniques (genie reduction, graph splitting, nonbacktracking propagation) that are likely to apply beyond SBMs.