The first dynamic algorithms for matrix rank and related objects achieve update times scaling with rank r, specifically Õ(r^1.405) per entry update and Õ(r^1.528 + z) per column update, extending to dynamic maximum matching.
Liu and Thatchaphol Saranurak and Aaron Sidford and Zhao Song and Di Wang , editor =
4 Pith papers cite this work, alongside 4 external citations. Polarity classification is still indexing.
4
Pith papers citing it
4
external citations · external index
years
2026 4representative citing papers
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
In an adaptive bin-deletion game, uniform redistribution and two-choice yield optimal O(n) recourse and O(log log n) load after n/2 rounds, and 2-splitting suffices for linear recourse.
citing papers explorer
-
Dynamic Rank, Basis, and Matching
The first dynamic algorithms for matrix rank and related objects achieve update times scaling with rank r, specifically Õ(r^1.405) per entry update and Õ(r^1.528 + z) per column update, extending to dynamic maximum matching.
-
Multi-Source Reachability in Near-Optimal Time
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
-
Random dimension reduction and learning symmetric properties of quantum states
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
-
Load Balancing under Adaptive Bin Deletions
In an adaptive bin-deletion game, uniform redistribution and two-choice yield optimal O(n) recourse and O(log log n) load after n/2 rounds, and 2-splitting suffices for linear recourse.