  We consider the algorithmic problem of community detection in networks. Given
an undirected friendship graph $G=\left(V,E\right)$, a subset $S\subseteq V$ is
an $\left(\alpha,\beta\right)$-community if:
  * Every member of the community is friends with an $\alpha$-fraction of the
community;
  * Every non-member is friends with at most a $\beta$-fraction of the
community.
  Arora et al [AGSS12] gave a quasi-polynomial time algorithm for enumerating
all the $\left(\alpha,\beta\right)$-communities for any constants
$\alpha>\beta$.
  Here, we prove that, assuming the Exponential Time Hypothesis (ETH),
quasi-polynomial time is in fact necessary - and even for a much weaker
approximation desideratum. Namely, distinguishing between:
  * $G$ contains an $\left(1,o\left(1\right)\right)$-community; and
  * $G$ does not contain an
$\left(\beta+o\left(1\right),\beta\right)$-community for any
$\beta\in\left[0,1\right]$.
  We also prove that counting the number of
$\left(1,o\left(1\right)\right)$-communities requires quasi-polynomial time
assuming the weaker #ETH.
