Computer Science/Discrete Mathematics Seminar I

Stochastic block models and probabilistic reductions

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.

Date & Time

November 28, 2016 | 11:15am – 12:15pm

Location

S-101

Affiliation

Princeton University