# The Algorithmic Phase Transition in Correlated Spiked Models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2025.

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

- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model](https://mlsanity.com/paper/2604.20907/) (2026)

## Abstract (arXiv)

We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices  X=tfracλ√n xutop+W, quad Y=tfracμ√n yvtop+Z  where the spikes x,y have correlation ρ. Specifically, we consider two fundamental models: (1) Correlated spiked Wigner model with signal-to-noise ratio λ,μ; (2) Correlated spiked n*N Wishart (covariance) model with signal-to-noise ratio √λ,√μ. We propose an efficient detection and estimation algorithm based on counting a specific family of edge-decorated cycles. The algorithm's performance is governed by the function  F(λ,μ,ρ,γ)=maxBig frac λ2  γ , frac μ2  γ , frac λ2 ρ2  γ-λ2+λ2 ρ2  + frac μ2 ρ2  γ-μ2+μ2 ρ2  Big ,.  We prove our algorithm succeeds for the correlated spiked Wigner model whenever F(λ,μ,ρ,1)>1, and succeeds for the correlated spiked Wishart model whenever F(λ,μ,ρ,tfracnN)>1. Our result shows that an algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either x from X alone or y from Y alone is believed to be computationally infeasible. We complement our algorithmic results with evidence for a matching computational lower bound. In particular, we prove that when F(λ,μ,ρ,1)<1 for the correlated spiked Wigner model and when F(λ,μ,ρ,tfracnN)<1 for the spiked Wishart model, all algorithms based on low-degree polynomials fails to distinguish (X,Y) with two independent noise matrices. This strongly suggests that F=1 is the precise computation threshold for our models.