The spectral meta-algorithm is optimally accurate in the geometric block model
Let be the geometric block model and suppose it has a giant component. Let denote an accuracy level, and let the spectral meta-algorithm be the algorithm described in the source.
Spectral meta-algorithm conjecture. For any and such that has a giant component, there exists such that the spectral meta-algorithm recovers communities with accuracy on , and no algorithm recovers communities with accuracy on .
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 while using 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
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.