Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs

Jian Ding, Hang Du, Zhangsong Li

Given two Erdős-Rényi graphs with $n$ vertices whose edges are correlated through a latent vertex correspondence, we study complexity lower bounds for the associated correlation de…