BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Connectivity in discrete random processes - Po-She
 n Loh (Carnegie-Mellon)
DTSTART;TZID=Europe/London:20110609T163000
DTEND;TZID=Europe/London:20110609T173000
UID:TALK31160AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/31160
DESCRIPTION:Half a century ago\, a seminal paper of Erdos and 
 Renyi launched the systematic study of random grap
 hs. Since then\, this direction of investigation h
 as blossomed into a broad field\, and the original
  model has given rise to many useful variants. Of 
 the properties which have received attention\, one
  of the most fundamental has been that of global c
 onnectivity.\n\nRecently\, motivated by the practi
 cal problem of establishing connectivity in peer-t
 o-peer networks\, a natural question of similar fl
 avor arose in the analysis of a natural randomized
  clustering algorithm. Using methods which origina
 ted from physics\, but now known to be remarkably 
 useful in the study of random graphs\, we establis
 h the asymptotic optimality of this algorithm. We 
 also prove the first rigorous lower bounds on the 
 performance of a closely-related algorithm\, exten
 ding an approach of Oded Schramm.\n\nJoint work wi
 th Eyal Lubetzky. 
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
 B
CONTACT:Berestycki
END:VEVENT
END:VCALENDAR