Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
Jian Ding, Hang Du, Zhangsong Li · arXiv (Cornell University) · 2023
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 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=o\big( \frac{\log n}{\log nq} \wedge \sqrt{\log n} \big)$ and the correlation $ρ<\sqrtα$ where $α\approx 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.