Rasmus Kyng

activity

20142026

most citedAlgorithms for Lipschitz Learning on Graphs

24 citations · 59 across the 29 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DS2021★ 1 cited

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

Given a directed, weighted graph $G = (V, E)$ undergoing edge insertions, the incremental single-source shortest paths (SSSP) problem asks for the maintenance of approximate distances…

math.OC2021★ 1 cited

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…

cs.DS2021

Almost-linear-time Weighted $ℓ_{p}$ -norm Solvers in Slightly Dense Graphs via Sparsification

Deeksha Adil, Brian Bullins, Rasmus Kyng +1

We give almost-linear-time algorithms for constructing sparsifiers with $n p o l y (lo g n)$ edges that approximately preserve weighted $(ℓ_{2}^{2} + ℓ_{p}^{p})$ flow or voltage obj…

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization

Almost-linear-time Weighted ℓp​-norm Solvers in Slightly Dense Graphs via Sparsification

Almost-linear-time Weighted $ℓ_{p}$ -norm Solvers in Slightly Dense Graphs via Sparsification