  Given two Erd\H{o}s-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(\rho^{-1})$ polynomial algorithm fails for detection, where $\rho$ 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 $\rho<\sqrt{\alpha}$ where
$\alpha\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.
