Yury Polyanskiy | Recent results on broadcasting on trees and stochastic block model
GRAMSIA 5/17/2023
Speaker: Yury Polyanskiy (MIT)
Title: Recent results on broadcasting on trees and stochastic block model
Abstract: I will survey recent results and open questions regarding the q-ary stochastic block model and its local version (broadcasting on trees, or BOT). For example, establishing uniqueness of non-trivial solution to distribution recursions (BP fixed point) implies a characterization for the limiting mutual information between the graph and community labels. For q=2 uniqueness holds in all regimes. For q (greater than)2* uniqueness is currently only proved above a certain threshold that is asymptotically (for large q) is close to Kesten-Stigum (KS) threshold. At the same time between the BOT reconstruction and KS we show that uniqueness does not hold, at least in the presence of (arbitrary small) vertex-level side information. I will also discuss extension of the robust reconstruction result of Janson-Mossel’2004.
Based on joint works with Qian Yu (Princeton) and Yuzhou Gu (MIT).
right angled bracket replaced with text since Youtube does not allow angled brackets in descriptions