Skip to content
DraconiticResearch
Search Sources API
178,033 studies31 sourcesUpdated 27 min ago
PreprintarXiv licencearXiv

A Simple Complexity Lower Bound for Solving Ax=b

  • Ohad Shamir
Open at sourcePDFDOICite

Abstract

In this note, we provide a short and direct proof that approximately solving Ax=b to relative error ε, where A has condition number κ and unrestricted dimension, requires Ω(κlog(1/ε)) 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 Ω(√κlog(1/ε)) lower bound for optimizing strongly convex quadratic functions, applicable to randomized algorithms.

Related

  1. A short proof of a quadratic lower bound on the border determinantal complexity of x1n+⋯+xnn over ℂ: A simple human exposition
    Karthik Sheshadri
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. A Universal Lower Bound for the Complexity of Gaussian-Divisible Spin Glasses
    Pax Kivimae, Benjamin McKenna
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  3. A Quadratic Lower Bound on Determinantal Complexity
    Mrinal Kumar, Ben Lee Volk
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
    Daniel Dadush, Zhuan Khye Koh, Bento Natura +2
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Non-Terminal Complexity of Simple Semi-Conditional Grammars
    Henning Fernau, Sanjay Jain, Linus Richter +2
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv

Cite

BibTeXRIS
BibTeX
@misc{shamir2026simple,
  title = {{A Simple Complexity Lower Bound for Solving $Ax=b$}},
  author = {Ohad Shamir},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.10874},
  eprint = {2609.10874},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10874},
}
RIS
TY  - UNPB
TI  - A Simple Complexity Lower Bound for Solving Ax=b
AU  - Ohad Shamir
PY  - 2026
DA  - 2026/09/09
PB  - arXiv
DO  - 10.48550/arxiv.2609.10874
UR  - https://arxiv.org/abs/2609.10874
AB  - In this note, we provide a short and direct proof that approximately solving Ax=b to relative error ε, where A has condition number κ and unrestricted dimension, requires Ω(κlog(1/ε)) 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 Ω(√κlog(1/ε)) lower bound for optimizing strongly convex quadratic functions, applicable to randomized algorithms.
ER  -