24 citations · 37 across the 5 of their papers we have counts for
12 papers
A Simple Framework for Finding Balanced Sparse Cuts via APSP
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg +1
We present a very simple and intuitive algorithm to find balanced sparse cuts in a graph via shortest-paths. Our algorithm combines a new multiplicative-weights framework for solvi…
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Li Chen, Rasmus Kyng, Yang P. Liu +3
We give an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with edges and polynomially bounded integral demands, costs, and capacities in…
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg +1
We study linear equations in combinatorial Laplacians of -dimensional simplicial complexes (-complexes), a natural generalization of graph Laplacians. Combinatorial Laplacian…
Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions
Ming Ding, Rasmus Kyng, Peng Zhang
We give a nearly-linear time reduction that encodes any linear program as a 2-commodity flow problem with only a small blow-up in size. Under mild assumptions similar to those empl…
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Given a directed, weighted graph undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances…
On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
Nicolas Emmenegger, Rasmus Kyng, Ahad N. Zehmakan
We prove lower bounds for higher-order methods in smooth non-convex finite-sum optimization. Our contribution is threefold: We first show that a deterministic algorithm cannot prof…