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.
Jiaming Xu received BE degree from Tsinghua University in Beijing (2009), and MS (2011) from UT-Austin, and PhD (2014) from UIUC, all in ECE. He is a postdoctoral fellow with the Statistics Department, the Wharton School of the University of Pennsylvania. His research interests are in stochastic networks.
(His homepage: http://www.ifp.illinois.edu/~jxu18/)