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
                                 will speak on
                   Stochastic Block Models and Reconstruction
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  <(>
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.
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <> 
Announcement from: Gady Kozma   <>