Delphi.science

From smoothed analysis to backward error: The power of adaptive perturbations

Source: arxiv.org/abs/2611.18545

Michał Dereziński, Michael W. Mahoney, Raphael A. Meyer, Christopher Musco

arXivarxiv/2611.18545Nov 13, 2026cs.DSscore 0

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$…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.18545
curl -X POST /api/v1/records/arxiv/2611.18545/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18545/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'