BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Information-theoretic bounds and phase transitions in community de
 tection and high-dimensional clustering - Cristopher Moore (Santa Fe Insti
 tute)
DTSTART:20160715T110000Z
DTEND:20160715T113000Z
UID:TALK66774@talks.cam.ac.uk
CONTACT:INI IT
DESCRIPTION:<span>Co-authors: Jess Banks (SFI/UC Berkeley)\, Jiaming  Xu (
 Simons)\, Joe Neeman (UT Austin)\, Praneeth Netrapalli  (MSR Cambridge) <b
 r></span> <br>Over the past decade\, a rich interaction has grown up betwe
 en statistical  physics and statistical inference. In particular\, physics
  often predicts phase  transitions where\, if a data set becomes too spars
 e or too noisy\, it suddenly  becomes impossible to find its underlying st
 ructure\, or even to distinguish it  from a &ldquo\;null model&rdquo\; wit
 h no structure at all. For instance\, in the community  detection problem 
 in networks\, there is a transition below which the vertices  cannot be la
 beled better than chance\, and the network cannot be distinguished  from a
 n Erdos-Renyi random graph. Similarly\, in the clustering problem in  Gaus
 sian mixture models\, it becomes impossible to find the clusters\, or even
  to  tell whether clusters exist\, i.e.\, to distinguish the data from a s
 ingle  Gaussian. <br> <br>Many of the physics predictions have been made r
 igorous\, but there is still a  very lively interchange between the fields
 \, both about these transitions and  about asymptotically optimal algorith
 ms. In particular\, while efficient  message-passing and spectral algorith
 ms are known that succeed down to the  so-called Kesten-Stigum bound\, in 
 a number of problems we believe that it is  information-theoretically poss
 ible (but perhaps not computationally feasible) to  go further. I will giv
 e a friendly introduction to this field\, and present some  new results pr
 oving this conjecture. <br> <span><br>This is joint work with Jess Banks\,
  Joe Neeman\, Praneeth Netrapalli\, and  Jiaming Xu.</span>
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR