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

arXiv: https://arxiv.org/abs/2311.15931 · HTML: https://mlsanity.com/paper/2311.15931/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2023.

## Built on by (most cited first, 11 of 11)

- [The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime](https://mlsanity.com/paper/2402.15095/) (2024)
- [Efficient Graph Matching for Correlated Stochastic Block Models](https://mlsanity.com/paper/2412.02661/) (2024)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [The feasibility of multi-graph alignment: a Bayesian approach](https://mlsanity.com/paper/2502.17142/) (2025)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Testing Dependency of Weighted Random Graphs](https://mlsanity.com/paper/2409.14870/) (2024)
- [Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm](https://mlsanity.com/paper/2412.16457/) (2024)
- [A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials](https://mlsanity.com/paper/2504.03097/) (2025)
- [A Smooth Computational Transition in Tensor PCA](https://mlsanity.com/paper/2509.09904/) (2025)
- [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025)

## Abstract (arXiv)

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.