The polynomial-time barrier below the Kesten–Stigum threshold

Let $k\in\mathbb{Z}_+$, let $p\in(0,1)^k$ be a probability distribution, and let $Q$ be a symmetric $k\times k$ matrix with nonnegative entries. Let $P$ be the diagonal matrix with $P_{i,i}=p_i$, and let $\lambda_1,\lambda_2$ be the leading eigenvalues of $PQ$ ordered by nonincreasing magnitude. Polynomial-time barrier conjecture. If $\lambda_2^2<\lambda_1$, then there is no polynomial-time algorithm that can solve weak recovery in a graph $G$ drawn from $\mathrm{SBM}(n,p,Q/n)$.

This conjecture formalizes the expected computational barrier below the Kesten–Stigum threshold in the general sparse stochastic block model. The source presents it as an open problem; the strict inequality leaves the threshold case itself outside the claim.