Decelle et al.'s achievability conjecture for stochastic block model detection

Let $(X,G)$ be drawn from the stochastic block model $\operatorname{SBM}(n,k,a,b)$: $X$ is uniformly drawn among partitions of $[n]$ into $k$ balanced clusters, and $G$ has vertex set $[n]$, with edges placed independently with probability $a/n$ inside clusters and $b/n$ across clusters. Define

$$\operatorname{SNR}=\frac{(a-b)^2}{k(a+(k-1)b)}.$$

An algorithm detects communities if, given $G$, it outputs a clustering $\hat{X}$ positively correlated with $X$ with high probability. Decelle et al.'s achievability conjecture. Irrespective of $k$, if $\operatorname{SNR}>1$, communities can be detected in polynomial time, so the Kesten–Stigum threshold is efficiently achievable. If $k\geq 4$, communities can also be detected information-theoretically for some $\operatorname{SNR}$ strictly below $1$; when imposing $a>b$, the conjecture requires $k\geq 5$. This conjecture concerns the computational and information-theoretic thresholds for community detection. The paper proves both parts: acyclic belief propagation achieves the Kesten–Stigum threshold efficiently, and a non-efficient typicality-sampling algorithm detects below it for $k=4$.