{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-23","reactions":{}}