Weak recovery threshold in the geometric block model

At least 7 years old · documented by

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,t≥0s,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.

References

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.