Weak recovery threshold in the geometric block model
Let denote the geometric block model, and suppose it has a giant component. Weak recovery means recovering the communities with nontrivial accuracy by an efficient algorithm.
Weak recovery threshold conjecture. Let and suppose has a giant component. Weak recovery is efficiently solvable in if and only if .
This conjecture proposes that any positive geometric separation suffices for efficient weak recovery, provided a giant component exists. The source gives no resolution, so the claim remains open.
References
Primary source
Emmanuel Abbe, Enric Boix, Peter Ralli and Colin Sandon, “Graph powering and spectral robustness”, arXiv:1809.04818 (2018).
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.