The Weizmann Institute of Science Faculty of Mathematics and Computer Science Geometric Functional Analysis and Probability Seminar Seminar Room, Room 261, Ziskind Building on Thursday, May 31, 2012 11:00 - 13:00 Elchanan Mossel Berkeley will speak on Stochastic Block Models and Reconstruction Abstract: I will sketch a proof of recent conjectures from theoretical physics regarding a variant of the Erdos-Reyni random graph G(n,p). The conjecture was made by: A. Decelle, F. Krzakala, C. Moore, L. Zdeborov <(http://arxiv.org/abs/1109.304)> The model under consideration was studied extensively in statistics since the 1980s as a model of communities (under the name of the ``block model''). Independently, since the 1980's the model was studied extensively in theoretical computer science in the context of planted graph problems under the name of the ``planted bisection problem''. The conjectures establish an exact threshold for tasks involving estimating the communities / finding the planted partition and other parameter of the model. A number of fascinating open problems will be presented. Joint work with J. Neeman and A. Sly. <http://arxiv.org/abs/1202.1499.> --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Gady Kozma <gady.kozma@weizmann.ac.il>