{"id":"arxiv/2610.08872","url":"https://arxiv.org/abs/2610.08872","tags":["cs.IT","cs.LG","math.PR","math.ST","stat.ML"],"score":0,"title":"Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models","domain":"cs.IT","source":"arxiv","authors":["Soroor Ghandali"],"reviews":0,"subject":"cs.IT","summary":"We study community recovery in the sparse symmetric stochastic block model with $q$ communities, average degree $d$ and signal strength $λ$ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold $dλ^2=1$ and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-$D$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}