  This paper studies the problem of detecting the presence of a small dense
community planted in a large Erd\H{o}s-R\'enyi random graph $\mathcal{G}(N,q)$,
where the edge probability within the community exceeds $q$ by a constant
factor. Assuming the hardness of the planted clique detection problem, we show
that the computational complexity of detecting the community exhibits the
following phase transition phenomenon: As the graph size $N$ grows and the
graph becomes sparser according to $q=N^{-\alpha}$, there exists a critical
value of $\alpha = \frac{2}{3}$, below which there exists a computationally
intensive procedure that can detect far smaller communities than any
computationally efficient procedure, and above which a linear-time procedure is
statistically optimal. The results also lead to the average-case hardness
results for recovering the dense community and approximating the densest
$K$-subgraph.
