67 citations · 176 across the 22 of their papers we have counts for
7 papers · 1 filter
Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric -Matrices
Arun Jambulapati, Kirankumar Shiragur, Aaron Sidford
In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either…
Near-optimal method for highly smooth convex optimization
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee +2
We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the order Taylor expansion of a function at t…
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression
Neha Gupta, Aaron Sidford
In this paper, we obtain improved running times for regression and top eigenvector computation for numerically sparse matrices. Given a data matrix …
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi +1
In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. e…
Towards Optimal Running Times for Optimal Transport
Jose Blanchet, Arun Jambulapati, Carson Kent +1
In this work, we provide faster algorithms for approximating the optimal transport distance, e.g. earth mover's distance, between two discrete probability distributions $μ, ν\in Δ^…