A computational transition for detecting correlated stochastic block models by low-degree polynomials

Guanyi Chen, Jian Ding, Shuyang Gong +1

Detection of correlation in a pair of random graphs is a fundamental statistical and computational problem that has been extensively studied in recent years. In this work, we consi…