Detecting communities is hard, and counting them is even harder

We consider the algorithmic problem of community detection in networks. Given an undirected friendship graph G=left(V,Eright), a subset Ssubseteq V is an left(α,βright)-community if: * Every member of the community is friends with an α-fraction of the community; * Every non-member is friends with at most a β-fraction of the community. Arora et al [AGSS12] gave a quasi-polynomial time algorithm for enumerating all the left(α,βright)-communities for any constants α>β. 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,oleft(1right)right)-community; and * G does not contain an left(β+oleft(1right),βright)-community for any β∈left[0,1right]. We also prove that counting the number of left(1,oleft(1right)right)-communities requires quasi-polynomial time assuming the weaker #ETH.