Computational Lower Bounds for Community Detection on Random Graphs

Bruce Hajek, Yihong Wu, Jiaming Xu

This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph $\mathcal{G}(N,q)$, where the edge probability withi…