{"id":"arxiv/2609.38101","url":"https://arxiv.org/abs/2609.38101","tags":["cs.DS","cs.CC","math.NA"],"score":0,"title":"Solving Linear Systems in $\\widetilde{O}(mn \\log \\fracκε)$ Bit Operations","domain":"cs.DS","source":"arxiv","authors":["Jonathan A. Kelner"],"reviews":0,"subject":"cs.DS","summary":"We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\\in\\mathbb{R}^{n\\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\\le1/2$ using $\\widetilde{O(}mn\\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\\widetilde{O}(n)$, this gives an $\\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}