Decelle–Krzakala–Moore–Zdeborová conjecture on stochastic block model detection
Let be the stochastic block model with communities, and set
Decelle–Krzakala–Moore–Zdeborová conjecture. For the block model: (I) for all , it is possible to detect communities better than random if ; (II) for , it is information theoretically impossible to predict better than random if and ; and (III) for , it is information theoretically possible to predict better than random for some with , but not in a computationally efficient way.
These predictions identify the Kesten–Stigum threshold and the conjectured computational-statistical gap in sparse community detection. The paper states that part I was established in subsequent work, while parts II and III had only partial rigorous support at this point.
References
- Elchanan Mossel, Allan Sly and Youngtak Sohn, “Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees”, arXiv:2212.03362 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.