Papers

Topics

Fast Algorithms

Flows in Almost Linear Time via Adaptive Preconditioning
with Richard Peng, Sushant Sachdeva, and Di Wang.
In STOC 2019.
Iterative Refinement for \(\ell_p\)-norm Regression
with Deeksha Adil, Richard Peng, and Sushant Sachdeva.
In SODA 2019.
Solving Directed Laplacians in Nearly Linear Time through Sparse LU Factorizations
with Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford.
In FOCS 2018.
Incomplete Nested Dissection
with Richard Peng, Robert Schwieterman, and Peng Zhang.
In STOC 2018.
Approximate Gaussian Elimination
Rasmus Kyng.
My PhD dissertation, 2017.
Sampling Random Spanning Trees Faster than Matrix Multiplication
with David Durfee, John Peebles, Anup B. Rao, and Sushant Sachdeva.
In STOC 2017.
A Framework for Analyzing Resparsification Algorithms
with Jakub Pachocki, Richard Peng, and Sushant Sachdeva.
In SODA 2017.
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
with Sushant Sachdeva.
In FOCS 2016.
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
with Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman.
In STOC 2016.
Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)-norms
with Anup B. Rao and 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
with Anup B. Rao, Daniel A. Spielman, and 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
with Michael B. Cohen, 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
with Michael B. Cohen, Jakub W. Pachocki, Richard Peng, and Anup B. Rao.
Stretching Stretch Stretching Stretch
Michael B. Cohen, Gary L. Miller, Jakub W. Pachocki, Richard Peng, and Shen Chen Xu.

Fine-grained Complexity Theory

Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard
with Di Wang and Peng Zhang.
In SODA 2020.
Conference
Hardness Results for Structured Linear Systems
with Peng Zhang.
In FOCS 2017. Won the Machtey Award for Best Student Paper.

Discrepancy Theory and Random Matrix Theory

Four Deviations Suffice for Rank 1 Matrices
with Kyle Luh and Zhao Song.
In Advances in Mathematics, Volume 375, 2 December 2020.
A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers
with Zhao Song.
In FOCS 2018.

Machine Learning Applications and Experiments

Fast, Provable Algorithms for Isotonic Regression in all \(\ell_p\)-norms
with Anup B. Rao and 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
with Anup B. Rao, Daniel A. Spielman, and Sushant Sachdeva.
In COLT 2015.
Our implementations of the lex-minimization algorithms are available on the YINSlex Github repository.