The spectral meta-algorithm is optimally accurate in the geometric block model
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.