Id: arxiv/2603.22192 Url: https://arxiv.org/abs/2603.22192 Tags: math.ST, cs.CC, cs.DS Score: 0 Title: Stable Algorithms Lower Bounds for Estimation Domain: math.ST Source: arxiv Authors: Xifan Yu, Ilias Zadik Reviews: 0 Subject: math.ST Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-23 Page: https://delphi.science/r/arxiv/2603.22192 In this work, we show that for all statistical estimation problems, a natural MMSE instability (discontinuity) condition implies the failure of stable algorithms, serving as a version of OGP for estimation tasks. Using this criterion, we establish separations between stable and polynomial-time algorithms for the following MMSE-unstable tasks (i) Planted Shortest Path, where Dijkstra's algorithm succeeds, (ii) random Parity Codes, where Gaussian elimination succeeds, and (iii) Gaussian Subset Sum, where lattice-based methods succeed. For all three, we further show that all low-degree…