24 citations · 59 across the 29 of their papers we have counts for
5 papers · 1 filter
Acceleration Meets Inverse Maintenance: Faster -Regression
Deeksha Adil, Shunhua Jiang, Rasmus Kyng
We propose a randomized multiplicative weight update (MWU) algorithm for regression that runs in time when…
Bootstrapping Dynamic APSP via Sparsification
Rasmus Kyng, Simon Meierhans, Gernot Zöcklein
We give a simple algorithm for the dynamic approximate All-Pairs Shortest Paths (APSP) problem. Given a graph with polynomially bounded edge lengths, our data struc…
A Simple Dynamic Spanner via APSP
Rasmus Kyng, Simon Meierhans, Gernot Zöcklein
We give a simple algorithm for maintaining a -approximate spanner of a graph with vertices as receives edge updates by reduction to the dynamic All-Pairs…
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, Rasmus Kyng +4
We give the first almost-linear total time algorithm for deciding if a flow of cost at most still exists in a directed graph, with edge costs and capacities, undergoing decreme…
Optimal Electrical Oblivious Routing on Expanders
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg +1
In this paper, we investigate the question of whether the electrical flow routing is a good oblivious routing scheme on an -edge graph that is a -expander, i.e.…