The BBP (Baik-Ben Arous-Péché) transition in the spiked Wigner model:
Y = (λ/n) vv^T + W/√n, W ~ GOE(n)
Statistical threshold λ_stat = 0: information-theoretically detectable for any λ > 0.
Algorithmic threshold λ_alg = 1 (BBP): top eigenvalue detaches from bulk Wigner semicircle iff λ > 1. Below λ = 1, the spike is buried; PCA/spectral methods fail.
This statistical-to-algorithmic gap [λ_stat, λ_alg] = (0, 1) appears across many problems: sparse PCA, community detection (Kesten-Stigum), planted SAT, stochastic block model. In the gap, solutions exist but no efficient algorithm is known. Believed to require exponential time (OGP / low-degree lower bounds).