# Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2021.

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

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Generalized Attention Flow: Feature Attribution for Transformer Models via Maximum Flow](https://mlsanity.com/paper/2502.15765/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including: 1. More efficient dynamic spectral vertex sparsification, achieved by faster length estimation of random walks in weighted graphs using Morris counters [Morris 1978, Nelson-Yu 2020]. 2. A direct reduction from detecting edges with large energy in dynamic electric flows to dynamic spectral vertex sparsifiers. 3. A procedure for turning algorithms for estimating a sequence of vectors under updates from an oblivious adversary to one that tolerates adaptive adversaries via the Gaussian-mechanism from differential privacy. Combining these pieces with modifications to prior robust interior point frameworks gives an algorithm that on graphs with m edges computes a mincost flow with edge costs and capacities in [1, U] in time widetildeO(m3/2-1/58 log2 U). In prior and independent work, [Axiotis-Mkadry-Vladu FOCS 2021] also obtained an improved algorithm for sparse mincost flows on capacitated graphs. Our algorithm implies a widetildeO(m3/2-1/58 log U) time maxflow algorithm, improving over the widetildeO(m3/2-1/328log U) time maxflow algorithm of [Gao-Liu-Peng FOCS 2021].