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.
Constructing a Distance Sensitivity Oracle in O(n
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
A simpler conditional-expectations derandomization yields (L,f)-RPCs with Õ(f L^{f+o(1)}) covering value and Õ(f^{5/2} L^{o(1)}) query time; a new randomized construction matches an improved lower bound of Õ((L/f)^f L^{o(1)}) when f = o(log L).
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.
-
Simpler and Improved Replacement Path Coverings
A simpler conditional-expectations derandomization yields (L,f)-RPCs with Õ(f L^{f+o(1)}) covering value and Õ(f^{5/2} L^{o(1)}) query time; a new randomized construction matches an improved lower bound of Õ((L/f)^f L^{o(1)}) when f = o(log L).