2 papers
cs.DS2025
Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
Guanyi Chen, Jian Ding, Shuyang Gong +1
Consider a pair of sparse correlated stochastic block models subsampled from a common parent stochastic block model with two symmetric communities,…
math.PR2025
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…