| Publication | Date of Publication | Type |
|---|
| Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations | 2025-08-12 | Paper |
| Matrix scaling and balancing via box constrained Newton's method and interior point methods | 2025-08-06 | Paper |
| Faster algorithms for computing the stationary distribution, simulating random walks, and more | 2025-08-06 | Paper |
| Ramanujan graphs in polynomial time | 2025-08-06 | Paper |
Solving Linear Programs in the Current Matrix Multiplication Time
Journal of the ACM | 2022-12-08 | Paper |
Metrical task systems on trees via mirror descent and unfair gluing
SIAM Journal on Computing | 2021-06-22 | Paper |
Online row sampling
Theory of Computing | 2021-04-01 | Paper |
Solving linear programs in the current matrix multiplication time
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
| Simple analyses of the sparse Johnson-Lindenstrauss transform | 2019-10-25 | Paper |
A Nearly-Linear Bound for Chasing Nested Convex Bodies
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Metrical task systems on trees via mirror descent and unfair gluing
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
\(k\)-server via multiscale entropic regularization
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
An homotopy method for l <sub>p</sub> regression provably beyond self-concordance and in input-sparsity time
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Solving 1-Laplacians in nearly linear time: collapsing and expanding a topological ball
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| Sparsity, variance and curvature in multi-armed bandits | 2019-02-06 | Paper |
Sparsity, variance and curvature in multi-armed bandits
(available as arXiv preprint) | 2019-02-06 | Paper |
Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Input sparsity time low-rank approximation via ridge leverage score sampling
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Nearly tight oblivious subspace embeddings by trace inequalities
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Online row sampling
(available as arXiv preprint) | 2018-04-19 | Paper |
Optimal Approximate Matrix Product in Terms of Stable Rank
(available as arXiv preprint) | 2017-12-19 | Paper |
Geometric median in nearly linear time
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Uniform sampling for matrix approximation
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Approximating nearest neighbor distances
Lecture Notes in Computer Science | 2015-10-30 | Paper |
Dimensionality reduction for \(k\)-means clustering and low rank approximation
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
\(\ell_p\) row sampling by Lewis weights
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
