Portrait of me

About Me

I'm spending the fall semester 2017 as a research fellow at the Simons Institute at UC Berkeley. In the spring 2018, I'll be joining the Theory of Computation Group at Harvard as a postdoc under Jelani Nelson.

I finished my PhD at the Department of Computer Science at Yale in the summer 2017, where I was advised by Daniel A. Spielman.

Before attending Yale, I received B.A. in Computer Science from the University of Cambridge in 2011.

My Curriculum Vitae (Nov, 2016).

Research Interests

My research is focused on fast algorithms and their applications to machine learning.

Papers

Approximate Gaussian Elimination
Rasmus Kyng.
My PhD dissertation.
Solving Directed Laplacians in Nearly Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford.
Manuscript. The result is available as Chapter 5 of my dissertation.
Hardness Results for Structured Linear Systems
Rasmus Kyng, Peng Zhang.
In FOCS 2017.
Sampling Random Spanning Trees Faster than Matrix Multiplication
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, Sushant Sachdeva.
In STOC 2017.
A Framework for Analyzing Resparsification Algorithms
Rasmus Kyng, Jakub Pachocki, Richard Peng, and Sushant Sachdeva.
In SODA 2017.
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
Rasmus Kyng, Sushant Sachdeva.
In FOCS 2016.
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, Daniel A. Spielman.
In STOC 2016.
Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)-norms
Rasmus Kyng, Anup B. Rao, Sushant Sachdeva.
In NIPS 2015.
Our implementation of the least-squares Isotonic regression algorithm is available on the Isotonic Github repository.
Algorithms for Lipschitz Learning on Graphs
Rasmus Kyng, Anup B. Rao, Daniel A. Spielman, Sushant Sachdeva.
In COLT 2015.
Our implementations of the lex-minimization algorithms are available on the YINSlex Github repository.
Solving SDD Linear Systems in Nearly \( m\log^{1/2}n \) Time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao and Shen Chen Xu.
In STOC 2014.
The paper Solving SDD Linear Systems in Nearly \( m\log^{1/2}n \) Time was a merged submission of the following two papers:
Preconditioning in Expectation
Michael B. Cohen, Rasmus Kyng, Jakub W. Pachocki, Richard Peng, and Anup B. Rao.
Stretching Stretch
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, and Shen Chen Xu.

Upcoming and Recent Talks

UC Berkeley; September 25th, 2017. Hardness Results for Structured Linear Systems.
Google Research Mountain View; August 2017. Hardness Results for Structured Linear Systems.
YPNG Seminar, Yale Department of Statistics and Data Science; July 2017. Approximate Gaussian Elimination.
MSR Redmond; January 2017. Regression, Elimination, and Sampling on Graphs.
University of Copenhagen; January 2017. Approximate Gaussian Elimination.
CMU; December 2016. Approximate Gaussian Elimination.
Georgia Tech; November 2016. Approximate Gaussian Elimination.
Princeton; October 2016. Approximate Gaussian Elimination.
UC Berkeley; October 2016. Approximate Gaussian Elimination.
Google Research NYC; October 2016. Approximate Gaussian Elimination.
FOCS, New Brunswick; October 2016. Approximate Gaussian Elimination.
MIT A&C Seminar; September 2016. Approximate Gaussian Elimination.
Aarhus University; September 2016. Lipschitz Learning on Graphs.
China Theory Week, Hong Kong; August 2016. Approximate Gaussian Elimination.
SIAM Annual Meeting, Boston; July 2016. Approximate Cholesky Factorization
STOC, Boston; June 2016. Sparsified Cholesky and Multigrid Solvers for Connection Laplacians.
IT University of Copenhagen; December 2015. Lipschitz Learning and Isotonic Regression on Graphs

Code

Laplacians.jl
Laplacians.jl is a Julia package containing graph algorithms, especially ones related to spectral and algebraic graph theory. It was started by Dan Spielman, and has contributions from Dan, Serban Stan, myself and several others.
YINSlex Github Repository
Our implementations of the lex-minimization algorithms from the paper Algorithms for Lipschitz Learning on Graphs . The code was written by Anup Rao, Sushant Sachdeva, Dan Spielman, and myself.
Isotonic Github Repository
An implementation of the least-squares Isotonic regression algorithm from the paper Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)-norms . The code was written by Anup Rao, Sushant Sachdeva, and myself.

Teaching

TA for AMTH/CPSC 462/562: Graphs and Networks. Fall 2013.
TA for CPSC 469/569: Randomized Algorithms. Spring 2013.
TA for CPSC 201: Introduction to Computer Science. Fall 2012.

Contact

I can be reached by email at

rj [last name] @ gmail.com

[last name] = kyng