From smoothed analysis to backward error: The power of adaptive perturbations
Source: arxiv.org/abs/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$…
Comments and reviews
No comments yet.
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}'