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.