BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/611
DTSTAMP:20230914T125931Z
SUMMARY:Community Detection in Networks: SDP Relaxations and Computational 
 Gaps
DESCRIPTION:Speaker: Yihong Wu (University of Illinois at Urbana-Champaign\
 n129\, Coordinated Science Lab MC 228\n1308 W. Main Street\nUrbana Illinoi
 s 61801\nUnited States of America)\n\nAbstract: \nAbstract: This talk focu
 ses on the problem of finding the underlying communities within a network 
 using only knowledge of network topology. We consider a generative model f
 or a network\, namely the planted cluster model\, which is a simple extens
 ion of the classical stochastic block model. We derive a semidefinite prog
 ramming (SDP) relaxation of the maximum likelihood estimator for recoverin
 g the planted clusters from the network. If the size of the community is l
 inear in the total number of vertices\, the performance guarantee of the S
 DP exactly matches the necessary information bound. However\, if the commu
 nity size is sub-linear in the total number of vertices\, the performance 
 guarantee of the SDP is far from the information limit. Building on averag
 e case reductions\, we show there exists a significant gap between the inf
 ormation limit and what can be achieved by computationally efficient proce
 dures\, conditioned on the assumptions that certain instances of the plant
 ed clique problem cannot be solved in randomized polynomial time (based on
  joint work\, available at 1406.6625\, 1412.6156 and 1502.07738\, with Bru
 ce Hajek (UIUC) and Jiaming Xu (Wharton)).\n
URL:https://www.tcs.tifr.res.in/web/events/611
DTSTART;TZID=Asia/Kolkata:20150728T143000
DTEND;TZID=Asia/Kolkata:20150728T153000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR