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
cs.IT, cs.LG, math.IT, math.PR, math.ST, stat.ML, stat.TH
Submitted: 2026-10-06
Updated: 2026-10-06
Comments: 36 pages, 4 figures, 6 tables
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Sources
- Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)
- Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities
- Stochastic block models with many communities and the Kesten--Stigum bound
- Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
Related papers
- Language Modeling is Monotone Compression
- Clipped Affine Policy: Low-Complexity Near-Optimal Online Power Control for Energy Harvesting Communications over Fading Channels
- Discrepancy for Random Linear Codes
- A New Approach to Code Smoothing Bounds
- Contextual Memory-Enhanced Source Coding for Low-SNR Communications
- Symmetry-Enforced Quadratic Approximate-Degradability Bounds for Noisy Landau-Streater Channels