Weak recovery threshold in the geometric block model

Let GBM(n,s,t)\mathrm{GBM}(n,s,t) 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 s,t0s,t\geq 0 and suppose GBM(n,s,t)\mathrm{GBM}(n,s,t) has a giant component. Weak recovery is efficiently solvable in GBM(n,s,t)\mathrm{GBM}(n,s,t) if and only if s>0s>0.

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

Never refreshed

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.