The noisy equitable stochastic block model detection conjecture
Let be the noise operator that rewires swaps of a -regular graph, and let be the equitable stochastic block model. Write for the distribution of when . For fixed , , , and , with , the noisy equitable stochastic block model detection conjecture. There is no polynomial-time algorithm that, with high probability as , distinguishes from . The divisibility condition ensures that the equitable model is defined for an infinite sequence of values of . This conjecture is used as a conditional hardness assumption for results on random regular graphs; the added rewiring noise is stated to be crucial to the conjecture's applicability.
References
- Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore and Alexander S. Wein, “Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs”, arXiv:2008.12237 (2020).
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.