A Simple Complexity Lower Bound for Solving $Ax=b$
In this note, we provide a short and direct proof that approximately solving $Ax=b$ to relative error $\varepsilon$, where $A$ has condition number $κ$ and unrestricted dimension, requires $Ω(κ\log(1/\varepsilon))$ matrix-vector multiplications in the worst case, even for randomized algorithms. This essentially recovers the lower bound of Dereziński, Epperly and Meyer [2026] for this setting, whose elegant and more general approach inspired us to seek a short direct proof. A straightforward reduction implies the classical $Ω(\sqrtκ\log(1/\varepsilon))$ lower bound for optimizing strongly…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.10874
curl -X POST /api/v1/records/arxiv/2609.10874/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.10874/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'