BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Connectivity in discrete random processes - Po-Shen Loh (Carnegie-
 Mellon)
DTSTART:20110609T153000Z
DTEND:20110609T163000Z
UID:TALK31160@talks.cam.ac.uk
CONTACT:Berestycki
DESCRIPTION:Half a century ago\, a seminal paper of Erdos and Renyi launch
 ed the systematic study of random graphs. Since then\, this direction of i
 nvestigation has 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 connectiv
 ity.\n\nRecently\, motivated by the practical problem of establishing conn
 ectivity in peer-to-peer networks\, a natural question of similar flavor a
 rose in the analysis of a natural randomized clustering algorithm. Using m
 ethods which originated from physics\, but now known to be remarkably usef
 ul in the study of random graphs\, we establish the asymptotic optimality 
 of this algorithm. We also prove the first rigorous lower bounds on the pe
 rformance of a closely-related algorithm\, extending an approach of Oded S
 chramm.\n\nJoint work with Eyal Lubetzky. 
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR