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

At least 7 years old · documented by

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.

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.