Reaching the thresholds for block models

The talk overviews our recent results on the stochastic block model thresholds, both for exact recovery (the CH-divergence threshold) and weak recovery (the Kesten-Stigum threshold). While Laplacians fail to achieve the KS threshold, it is shown that Acyclic BP - or equivalently a spectral method on a nonbacktracking operator of generalized order - achieves the threshold in quasi linear time. It is also shown that starting from 5 communities, information theoretic methods can cross the KS threshold. Joint works with C. Sandon:http://arxiv.org/abs/1503.00609 http://arxiv.org/abs/1512.09080