{"id":"arxiv/2609.30853","url":"https://arxiv.org/abs/2609.30853","tags":["math.OC","cs.DS"],"score":0,"title":"Faster Linear Programming with $\\sqrt{\\mathrm{rank}}$ Linear System Solves","domain":"math.OC","source":"arxiv","authors":["Zhao Song"],"reviews":0,"subject":"math.OC","summary":"Lee and Sidford [LS19] showed that the linear program $\\min\\{c^\\top x\\ :\\ A^\\top x=b,\\ l\\leq x\\leq u\\}$ over $x\\in\\mathbb{R}^m$, where $A\\in\\mathbb{R}^{m\\times n}$, can be solved to accuracy $ε$ using $O(\\sqrt n\\log^{13}m\\cdot\\log(mU/ε))$ solves of linear systems in $A^\\top\\mathbf DA$ for positive diagonal matrices $\\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\\log^{13}m$ factor is an interesting future…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}