Weak recovery threshold in the geometric block model
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.