24 citations · 151 across the 43 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 1 cited
A Framework for Analyzing Resparsification Algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng +1
A spectral sparsifier of a graph is a sparser graph that approximately preserves the quadratic form of , i.e. for all vectors , , where $…
cs.DS2016
Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, John Peebles +2
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in time (The $\tilde{…
cs.DS2016
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
Rasmus Kyng, Sushant Sachdeva
We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix w…