Rasmus Kyng

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 60

Top Topics

Matrix Inversion

Top Venues

Publications

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
Optimal Electrical Oblivious Routing on Expanders. ICALP (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. CoRR (2024)
Yves Baumann, Rasmus Kyng
A Framework for Parallelizing Approximate Gaussian Elimination. SPAA (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. SODA (2024)
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
Optimal Electrical Oblivious Routing on Expanders. CoRR (2024)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications. STOC (2024)
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. STOC (2024)
Yuan Gao, Rasmus Kyng, Daniel A. Spielman
Robust and Practical Solution of Laplacian Equations by Approximate Elimination. CoRR (2023)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications. CoRR (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. CoRR (2023)
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu
Maintaining Expander Decompositions via Sparse Cuts. SODA (2023)
Jan Van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. FOCS (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. CoRR (2023)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow. Commun. ACM 66 (12) (2023)
Rasmus Kyng
An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). ICALP (2023)
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. CoRR (2023)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. SOSA (2023)
Nicolas Emmenegger, Rasmus Kyng, Ahad N. Zehmakan
On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization. AISTATS (2022)
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu
Maintaining Expander Decompositions via Sparse Cuts. CoRR (2022)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. FOCS (2022)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. CoRR (2022)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. CoRR (2022)
Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva
-Regression. CoRR (2022)
Tali Kaufman, Rasmus Kyng, Federico Soldà
-Independence. SODA (2022)
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. CoRR (2022)
Ming Ding, Rasmus Kyng, Peng Zhang
Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions. CoRR (2022)
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. ICALP (2022)
Rasmus Kyng, Simon Meierhans, Maximilian Probst
Derandomizing Directed Random Walks in Almost-Linear Time. FOCS (2022)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Derandomizing Directed Random Walks in Almost-Linear Time. CoRR (2022)
Sílvia Casacuberta, Rasmus Kyng
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. ITCS (2022)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. SODA (2022)
Ming Ding, Rasmus Kyng, Peng Zhang
Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. ICALP (2022)
Tali Kaufman, Rasmus Kyng, Federico Soldà
-Independence. CoRR (2021)
Nicolas Emmenegger, Rasmus Kyng, Ahad N. Zehmakan
On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization. CoRR (2021)
Sílvia Casacuberta, Rasmus Kyng
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. CoRR (2021)
Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva
-norm Solvers in Slightly Dense Graphs via Sparsification. CoRR (2021)
Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva
-Norm Solvers in Slightly Dense Graphs via Sparsification. ICALP (2021)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. CoRR (2021)
Rasmus Kyng, Peng Zhang
Hardness Results for Structured Linear Systems. SIAM J. Comput. 49 (4) (2020)
Rasmus Kyng, Di Wang, Peng Zhang
Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard. SODA (2020)
Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva
Iterative Refinement for ℓp-norm Regression. SODA (2019)
Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang
Flows in almost linear time via adaptive preconditioning. STOC (2019)
Rasmus Kyng, Kyle Luh, Zhao Song
Four Deviations Suffice for Rank 1 Matrices. CoRR (2019)
Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang
Flows in Almost Linear Time via Adaptive Preconditioning. CoRR (2019)
Deeksha Adil, Rasmus Kyng, Richard Peng, Sushant Sachdeva
-norm Regression. CoRR (2019)
Rasmus Kyng, Zhao Song
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. CoRR (2018)
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. FOCS (2018)
Rasmus Kyng, Zhao Song
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees. FOCS (2018)
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations. CoRR (2018)
Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang
Incomplete nested dissection. STOC (2018)
Rasmus Kyng, Richard Peng, Robert Schwieterman, Peng Zhang
Incomplete Nested Dissection. CoRR (2018)
Rasmus Kyng, Peng Zhang
Hardness Results for Structured Linear Systems. CoRR (2017)
Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva
A Framework for Analyzing Resparsification Algorithms. SODA (2017)
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva
Sampling random spanning trees faster than matrix multiplication. STOC (2017)
Rasmus Kyng, Peng Zhang
Hardness Results for Structured Linear Systems. FOCS (2017)
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva
Sampling Random Spanning Trees Faster than Matrix Multiplication. CoRR (2016)
Rasmus Kyng, Jakub Pachocki, Richard Peng, Sushant Sachdeva
A Framework for Analyzing Resparsification Algorithms. CoRR (2016)
Rasmus Kyng, Sushant Sachdeva
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple. CoRR (2016)
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman
Sparsified Cholesky and multigrid solvers for connection laplacians. STOC (2016)
Rasmus Kyng, Sushant Sachdeva
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. FOCS (2016)
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians. CoRR (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman
Algorithms for Lipschitz Learning on Graphs. CoRR (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva
-norms. CoRR (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva
Fast, Provable Algorithms for Isotonic Regression in all L_p-norms. NIPS (2015)
Rasmus Kyng, Anup Rao, Sushant Sachdeva, Daniel A. Spielman
Algorithms for Lipschitz Learning on Graphs. COLT (2015)
Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki, Richard Peng, Anup B. Rao
Preconditioning in Expectation. CoRR (2014)
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, Shen Chen Xu
time. STOC (2014)