Events
Spring 2016
Counting Program Seminar Series
Friday, April 15th, 2016, 2:00 pm–3:00 pm
Parent Program:
Speaker:
Jiaming Xu (University of Pennsylvania)
Location:
Calvin Lab Room 116
Finding a Hidden Community in Networks: Where is the Hard Regime?
We consider the problem of recovering a hidden, dense community in a large network. The following two fundamental limits are of particular interest:
(1) Information limit: From an information-theoretic perspective, computational considerations aside, what are the fundamental limits of recovery?
(2) Computation limit: From a computational perspective, what are the fundamental limits of recovery in polynomial, or linear time?
This talk will present an overview and our recent results toward understanding these two fundamental limits. Based on joint work with Bruce Hajek and Yihong Wu from UIUC.
