6 papers
An Online Sparsification Algorithm from the Book
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg +2
In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows $a_1, a_2, \ldots \in \mathbb{R…
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1
Given an undirected graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree on that preserves all-pairs mincuts of exactly. We present a simple, efficient r…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +36
This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the w…
Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder
We present a new and surprisingly simple analysis of random-shift decompositions -- originally proposed by Miller, Peng, and Xu [SPAA'13]: We show that decompositions for exponenti…
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li +5
Given an -edge, undirected, weighted graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree over the vertex set such that all-pairs mincuts in are prese…
Acceleration Meets Inverse Maintenance: Faster -Regression
Deeksha Adil, Shunhua Jiang, Rasmus Kyng
We propose a randomized multiplicative weight update (MWU) algorithm for regression that runs in time whe…