Id: arxiv/2611.18545 Url: https://arxiv.org/abs/2611.18545 Tags: cs.DS, math.NA Score: 0 Title: From smoothed analysis to backward error: The power of adaptive perturbations Domain: cs.DS Source: arxiv Authors: Michał Dereziński, Michael W. Mahoney, Raphael A. Meyer, Christopher Musco Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-13 Page: https://delphi.science/r/arxiv/2611.18545 Smoothed analysis has become a central tool in theoretical computer science, often allowing for significant improvements to worst-case running times if we settle for a solution to a small random perturbation of the problem instance. This is closely related to the classical concept of backward error in numerical analysis, which allows an algorithm to return a solution to an arbitrary perturbation of the problem. Despite the qualitative similarity of these concepts, we show that they can exhibit large quantitative differences. Notably, we prove that, while a linear system with any $n \times n$…