Rasmus Kyng

According to our database, Rasmus Kyng authored at least 39 papers between 2014 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow.

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Commun. ACM, December, 2023

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow.

Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg

CoRR, 2023

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications.

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

CoRR, 2023

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

CoRR, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.

Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

CoRR, 2023

Robust and Practical Solution of Laplacian Equations by Approximate Elimination.

Yuan Gao, Rasmus Kyng, Daniel A. Spielman

CoRR, 2023

A Simple Framework for Finding Balanced Sparse Cuts via APSP.

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Maintaining Expander Decompositions via Sparse Cuts.

Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk).

Rasmus Kyng

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.

Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Fast Algorithms for 𝓁_p-Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

CoRR, 2022

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier.

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Scalar and Matrix Chernoff Bounds from ℓ_∞-Independence.

Tali Kaufman, Rasmus Kyng, Federico Soldà

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields.

Sílvia Casacuberta, Rasmus Kyng

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets.

Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions.

Ming Ding, Rasmus Kyng, Peng Zhang

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Derandomizing Directed Random Walks in Almost-Linear Time.

Rasmus Kyng, Simon Meierhans, Maximilian Probst

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

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

Nicolas Emmenegger, Rasmus Kyng, Ahad N. Zehmakan

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Almost-Linear-Time Weighted 𝓁_p-Norm Solvers in Slightly Dense Graphs via Sparsification.

Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Hardness Results for Structured Linear Systems.

Rasmus Kyng, Peng Zhang

SIAM J. Comput., 2020

Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard.

Rasmus Kyng, Di Wang, Peng Zhang

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Iterative Refinement for 𝓁_p-norm Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

CoRR, 2019

Four Deviations Suffice for Rank 1 Matrices.

Rasmus Kyng, Kyle Luh, Zhao Song

CoRR, 2019

Flows in almost linear time via adaptive preconditioning.

Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Iterative Refinement for ℓp-norm Regression.

Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Incomplete nested dissection.

Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees.

Rasmus Kyng, Zhao Song

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations.

Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Sampling random spanning trees faster than matrix multiplication.

David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A Framework for Analyzing Resparsification Algorithms.

Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Sparsified Cholesky and multigrid solvers for connection laplacians.

Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple.

Rasmus Kyng, Sushant Sachdeva

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Fast, Provable Algorithms for Isotonic Regression in all ℓ_p-norms.

Rasmus Kyng, Anup Rao, Sushant Sachdeva

CoRR, 2015

Fast, Provable Algorithms for Isotonic Regression in all L_p-norms.

Rasmus Kyng, Anup Rao, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Algorithms for Lipschitz Learning on Graphs.

Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Preconditioning in Expectation.

Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki, Richard Peng, Anup B. Rao

CoRR, 2014

Solving SDD linear systems in nearly <i>m</i>log^1/2<i>n</i> time.

Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu

Proceedings of the Symposium on Theory of Computing, 2014