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>