wovepaper — the arXiv observatory

papers

Publications (43)

cs.CY2025

Assessing GPT Performance in a Proof-Based University-Level Course Under Blind Grading

Ming Ding, Rasmus Kyng, Federico Solda +1

cs.DS2021

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

cs.DS2022

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

SÃlvia Casacuberta, Rasmus Kyng

math.CO2020

Four Deviations Suffice for Rank 1 Matrices

Rasmus Kyng, Kyle Luh, Zhao Song

cs.CC2017

Hardness Results for Structured Linear Systems

Rasmus Kyng, Peng Zhang

cs.DS2019

Flows in Almost Linear Time via Adaptive Preconditioning

Rasmus Kyng, Richard Peng, Sushant Sachdeva +1

cs.DS2022

A Simple Framework for Finding Balanced Sparse Cuts via APSP

Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg +1

cs.DS2024

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

Jan van den Brand, Li Chen, Rasmus Kyng +4

math.NA2026

Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop

Noah Amsel, Yves Baumann, Paul Beckman +33

cs.DS2025

Deterministic Almost-Linear-Time Gomory-Hu Trees

Amir Abboud, Rasmus Kyng, Jason Li +5

cs.DS2026

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1

cs.DS2016

A Framework for Analyzing Resparsification Algorithms

Rasmus Kyng, Jakub Pachocki, Richard Peng +1

cs.DS2018

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

Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4

cs.DS2024

Bootstrapping Dynamic APSP via Sparsification

Rasmus Kyng, Simon Meierhans, Gernot ZÃ¶cklein

math.OC2021

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

Nicolas Emmenegger, Rasmus Kyng, Ahad N. Zehmakan

cs.DS2023

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 +2

cs.DS2018

Incomplete Nested Dissection

Rasmus Kyng, Richard Peng, Robert Schwieterman +1

cs.DS2024

A Simple Dynamic Spanner via APSP

Rasmus Kyng, Simon Meierhans, Gernot ZÃ¶cklein

cs.LG2015

Algorithms for Lipschitz Learning on Graphs

Rasmus Kyng, Anup Rao, Sushant Sachdeva +1

cs.DS2017

Sampling Random Spanning Trees Faster than Matrix Multiplication

David Durfee, Rasmus Kyng, John Peebles +2

cs.DS2024

Optimal Electrical Oblivious Routing on Expanders

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg +1

cs.DS2022

Derandomizing Directed Random Walks in Almost-Linear Time

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

cs.DS2023

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

Jan van den Brand, Li Chen, Rasmus Kyng +5

cs.DS2023

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

Jan van den Brand, Li Chen, Rasmus Kyng +5

math.NA2023

Robust and Practical Solution of Laplacian Equations by Approximate Elimination

Yuan Gao, Rasmus Kyng, Daniel A. Spielman

math.PR2018

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

Rasmus Kyng, Zhao Song

cs.DM2022

Scalar and Matrix Chernoff Bounds from $ℓ_{\infty}$ -Independence

Tali Kaufman, Rasmus Kyng, Federico SoldÃ¡

cs.DS2023

Fast Algorithms for $ℓ_{p}$ -Regression

Deeksha Adil, Rasmus Kyng, Richard Peng +1

cs.DS2025

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings

Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder

cs.DS2023

Maintaining Expander Decompositions via Sparse Cuts

Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg +1

cs.DS2022

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

Li Chen, Rasmus Kyng, Yang P. Liu +3

cs.DS2026

An Online Sparsification Algorithm from the Book

Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2

cs.CC2022

Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions

Ming Ding, Rasmus Kyng, Peng Zhang

cs.DS2025

Acceleration Meets Inverse Maintenance: Faster $ℓ_{\infty}$ -Regression

Deeksha Adil, Shunhua Jiang, Rasmus Kyng

cs.DS2015

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

Rasmus Kyng, Yin Tat Lee, Richard Peng +2

cs.DS2025

Acceleration for Distributed Transshipment and Parallel Maximum Flow

Christoph Grunau, Rasmus Kyng, Goran Zuzic

cs.DS2021

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

Deeksha Adil, Brian Bullins, Rasmus Kyng +1

cs.DS2023

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

Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg

cs.DS2016

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

Rasmus Kyng, Sushant Sachdeva

cs.DS2019

Iterative Refinement for $ℓ_{p}$ -norm Regression

Deeksha Adil, Rasmus Kyng, Richard Peng +1

cs.CC2022

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

Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg +1

cs.LG2015

Fast, Provable Algorithms for Isotonic Regression in all $ℓ_{p}$ -norms

Rasmus Kyng, Anup Rao, Sushant Sachdeva

cs.DS2014

Preconditioning in Expectation

Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki +2

Publications (43)

Assessing GPT Performance in a Proof-Based University-Level Course Under Blind Grading

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

Four Deviations Suffice for Rank 1 Matrices

Hardness Results for Structured Linear Systems

Flows in Almost Linear Time via Adaptive Preconditioning

A Simple Framework for Finding Balanced Sparse Cuts via APSP

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop

Deterministic Almost-Linear-Time Gomory-Hu Trees

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

A Framework for Analyzing Resparsification Algorithms

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

Bootstrapping Dynamic APSP via Sparsification

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

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

Incomplete Nested Dissection

A Simple Dynamic Spanner via APSP

Algorithms for Lipschitz Learning on Graphs

Sampling Random Spanning Trees Faster than Matrix Multiplication

Optimal Electrical Oblivious Routing on Expanders

Derandomizing Directed Random Walks in Almost-Linear Time

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

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

Robust and Practical Solution of Laplacian Equations by Approximate Elimination

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

Scalar and Matrix Chernoff Bounds from ℓ∞​-Independence

Fast Algorithms for ℓp​-Regression

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings

Maintaining Expander Decompositions via Sparse Cuts

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

An Online Sparsification Algorithm from the Book

Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions

Acceleration Meets Inverse Maintenance: Faster ℓ∞​-Regression

Sparsified Cholesky and Multigrid Solvers for Connection Laplacians

Acceleration for Distributed Transshipment and Parallel Maximum Flow

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

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

Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

Iterative Refinement for ℓp​-norm Regression

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

Fast, Provable Algorithms for Isotonic Regression in all ℓp​-norms

Preconditioning in Expectation

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

Scalar and Matrix Chernoff Bounds from $ℓ_{\infty}$ -Independence

Fast Algorithms for $ℓ_{p}$ -Regression

Acceleration Meets Inverse Maintenance: Faster $ℓ_{\infty}$ -Regression

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

Iterative Refinement for $ℓ_{p}$ -norm Regression

Fast, Provable Algorithms for Isotonic Regression in all $ℓ_{p}$ -norms