# Statistical-computational gap in multiple Gaussian graph alignment

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 29 Nov 2025.

## Builds on (most cited first, 24 of 24)

- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Partial recovery bounds for clustering with the relaxed Kmeans](https://mlsanity.com/paper/1807.07547/) (2018)
- [Random graph matching at Otter's threshold via counting chandeliers](https://mlsanity.com/paper/2209.12313/) (2022)
- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Sharp threshold for alignment of graph databases with Gaussian weights](https://mlsanity.com/paper/2010.16295/) (2020)
- [Random Graph Matching with Improved Noise Robustness](https://mlsanity.com/paper/2101.11783/) (2021)
- [Correlation detection in trees for planted graph alignment](https://mlsanity.com/paper/2107.07623/) (2021)
- [Minimax rates in permutation estimation for feature matching](https://mlsanity.com/paper/1310.4661/) (2013)
- [Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm](https://mlsanity.com/paper/1403.7721/) (2014)
- [Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering](https://mlsanity.com/paper/1610.02918/) (2016)
- [Statistical limits of correlation detection in trees](https://mlsanity.com/paper/2209.13723/) (2022)
- [Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphs](https://mlsanity.com/paper/2311.15931/) (2023)
- [A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation](https://mlsanity.com/paper/2212.13677/) (2022)
- [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025)
- [Sharp Phase Transitions in Estimation with Low-Degree Polynomials](https://mlsanity.com/paper/2502.14407/) (2025)
- [Spectral Alignment of Correlated Gaussian matrices](https://mlsanity.com/paper/1912.00231/) (2019)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Computational lower bounds in latent models: clustering, sparse-clustering, biclustering](https://mlsanity.com/paper/2506.13647/) (2025)
- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [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)

## Abstract (arXiv)

We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vassaux and Massouli'e (2025) to regimes where the number of observed graphs p may also grow with the number of nodes n: when p ≤ O(n/log(n)), we recover the results from Vassaux and Massouli'e (2025), and p ≥ Omega(n/log(n)) corresponds to a regime where the problem is as difficult as aligning one single graph with some unknown "signal" graph. Moreover, when log p = ω(log n), the informational thresholds for partial and exact recovery no longer coincide, in contrast to the all-or-nothing phenomenon observed when log p=O(log n). Then, we provide the first computational barrier in the low-degree framework for (multiple) Gaussian graph alignment. We prove that when the correlation ρ is less than 1, up to logarithmic terms, low degree non-trivial estimation fails. Our results suggest that the task of aligning p graphs in polynomial time is as hard as the problem of aligning two graphs in polynomial time, up to logarithmic factors. These results characterize the existence of a statistical-computational gap and provide another example in which polynomial-time algorithms cannot handle complex combinatorial bi-dimensional structures.