Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphs

Given two ErdHos-R'enyi graphs with n vertices whose edges are correlated through a latent vertex correspondence, we study complexity lower bounds for the associated correlation detection problem for the class of low-degree polynomial algorithms. We provide evidence that any degree-O(ρ-1) polynomial algorithm fails for detection, where ρ is the edge correlation. Furthermore, in the sparse regime where the edge density q=n-1+o(1), we provide evidence that any degree-d polynomial algorithm fails for detection, as long as log d=obig( fraclog nlog nq wedge √log n big) and the correlation ρ<√α where α≈ 0.338 is the Otter's constant. Our result suggests that several state-of-the-art algorithms on correlation detection and exact matching recovery may be essentially the best possible.