Low-degree hardness of detection for correlated Erdős–Rényi graphs
研究了两个顶点一一对应的相关埃尔德什-雷尼图在低度多项式算法下的检测困难性，证明在特定条件下低度算法无法成功检测，暗示现有算法可能已是最优。
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 prove that no degree-O(ρ−1) polynomial algorithm can succeed for detection under an appropriate definition of success, where ρ is the edge correlation. Furthermore, in the sparse regime where the edge density q=n−1+o(1), we prove that no degree-d polynomial algorithm can succeed for detection under an appropriate definition of success, as long as d=exp(o( logn lognq∧logn)) 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.