Stochastic block models and probabilistic reductions

Computer Science/Discrete Mathematics Seminar I
Topic:Stochastic block models and probabilistic reductions
Speaker:Emmanuel Abbe
Affiliation:Princeton University
Date:Monday, November 28
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2016/1128-EmmanuelAbbe

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.