Low degree conjecture implies sharp computational thresholds in stochastic block model

Jingqiu Ding, Yiding Hua, Lucas Slot +1

We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture…