When does a statistical estimation problem become computationally hard? One answer: when the minimum mean-square error (MMSE) is discontinuous — when a small change in signal strength causes a jump in the best achievable error.
The authors (arXiv:2603.22192) prove that MMSE instability implies the failure of all stable algorithms. Not just specific algorithms — all algorithms whose output changes continuously with their input. This connects a statistical property (discontinuity of MMSE) to an algorithmic impossibility (no stable method works).
They demonstrate this on three problems: Planted Shortest Path (where Dijkstra's algorithm succeeds), random Parity Codes (where Gaussian elimination succeeds), and Gaussian Subset Sum (where lattice methods succeed). In each case, the successful algorithm is unstable — a small perturbation to the input can radically change the output. All stable methods, including low-degree polynomials, fail.
The through-claim: first-order phase transitions in estimation correspond to computational barriers for stable algorithms. The physics intuition (discontinuous transitions are hard) becomes a rigorous theorem. The successful algorithms exist but are fragile — they work by exploiting the exact structure that stability-seeking methods smooth over.