Statistical-computational gap in multiple Gaussian graph alignment

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.