# Solving Linear Programs with Sqrt(rank) Linear System Solves

arXiv: https://arxiv.org/abs/1910.08033 · HTML: https://mlsanity.com/paper/1910.08033/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2019.

## Built on by (most cited first, 15 of 15)

- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17796/) (2024)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Sampling with Barriers: Faster Mixing via Lewis Weights](https://mlsanity.com/paper/2303.00480/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Generalized Attention Flow: Feature Attribution for Transformer Models via Maximum Flow](https://mlsanity.com/paper/2502.15765/) (2025)
- [Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk](https://mlsanity.com/paper/2410.05700/) (2024)
- [Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis](https://mlsanity.com/paper/2412.11303/) (2024)
- [Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk](https://mlsanity.com/paper/2206.09384/) (2022)
- [Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling](https://mlsanity.com/paper/2307.12943/) (2023)
- [Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Data](https://mlsanity.com/paper/2506.20141/) (2025)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization](https://mlsanity.com/paper/2312.03218/) (2023)
- [A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra](https://mlsanity.com/paper/2608.25273/) (2026)

## Abstract (arXiv)

We present an algorithm that given a linear program with n variables, m constraints, and constraint matrix A, computes an ε-approximate solution in tildeO(√rank(A)log(1/ε)) iterations with high probability. Each iteration of our method consists of solving tildeO(1) linear systems and additional nearly linear time computation, improving by a factor of tildeOmega((m/rank(A))1/2) over the previous fastest method with this iteration cost due to Renegar (1988). Further, we provide a deterministic polynomial time computable tildeO(rank(A))-self-concordant barrier function for the polytope, resolving an open question of Nesterov and Nemirovski (1994) on the theory of "universal barriers" for interior point methods. Applying our techniques to the linear program formulation of maximum flow yields an tildeO(|E|√|V|log(U)) time algorithm for solving the maximum flow problem on directed graphs with |E| edges, |V| vertices, and integer capacities of size at most U. This improves upon the previous fastest polynomial running time of O(|E|min|E|1/2,|V|2/3log(|V|2/|E|)log(U)) achieved by Goldberg and Rao (1998). In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times of O(|E|min|E|1/2,|V|2/3) achieved by Even and Tarjan (1975) and Karzanov (1973) and of tildeO(|E|10/7) achieved more recently by Mkadry (2013).