The spectral meta-algorithm is optimally accurate in the geometric block model

Let GBM(n,s,t)\mathrm{GBM}(n,s,t) be the geometric block model and suppose it has a giant component. Let δ\delta denote an accuracy level, and let the spectral meta-algorithm be the algorithm described in the source.

Spectral meta-algorithm conjecture. For any ss and rr such that GBM(n,s,t)\mathrm{GBM}(n,s,t) has a giant component, there exists δ>1/2\delta>1/2 such that the spectral meta-algorithm recovers communities with accuracy δ\delta on GBM(n,s,t)\mathrm{GBM}(n,s,t), and no algorithm recovers communities with accuracy δ+Ω(1)\delta+\Omega(1) on GBM(n,s,t)\mathrm{GBM}(n,s,t).

The claim is intended to say that the spectral meta-algorithm attains optimal accuracy in the geometric block model. The source gives no resolution. The statement has an apparent parameter mismatch, mentioning rr while using tt in the model.

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.