# Flows in Almost Linear Time via Adaptive Preconditioning

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

## Key facts

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

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

- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [Functional Stochastic Localization](https://mlsanity.com/paper/2602.03999/) (2026)
- [A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in p](https://mlsanity.com/paper/2607.03503/) (2026)

## Abstract (arXiv)

We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to (1 + 1 / poly(n)) accuracy in almost-linear time. These problems include ℓp-norm minimizing flow for p large (p ∈ [ω(1), o(log2/3 n) ]), and their duals, ℓp-norm semi-supervised learning for p close to 1. As p tends to infinity, ℓp-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. This algorithm demonstrates that many tools previous viewed as limited to linear systems are in fact applicable to a much wider range of convex objectives. It is based on the the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC '04, SIMAX '14), but require several new tools: adaptive non-linear preconditioning, tree-routing based ultra-sparsification for mixed ℓ2 and ℓp norm objectives, and decomposing graphs into uniform expanders.