
Robust Regression Revisited: Acceleration and Improved Estimation Rates
We study fast algorithms for statistical regression problems under the s...
read it

Stochastic BiasReduced Gradient Methods
We develop a new primitive for stochastic optimization: a lowbias, low...
read it

Thinking Inside the Ball: NearOptimal Minimization of the Maximal Loss
We characterize the complexity of minimizing max_i∈[N] f_i(x) for convex...
read it

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
In this paper we provide an O(m (loglog n)^O(1)log(1/ϵ))expected time a...
read it

Robust SubGaussian Principal Component Analysis and WidthIndependent Schatten Packing
We develop two methods for the following fundamental statistical task: g...
read it

Acceleration with a Ball Optimization Oracle
Consider an oracle which takes a point x and returns the minimizer of a ...
read it

Positive Semidefinite Programming: Mixed, Parallel, and WidthIndependent
We give the first approximation algorithm for mixed packing and covering...
read it

A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport
Optimal transportation, or computing the Wasserstein or “earth mover's” ...
read it

Parallel Reachability in Almost Linear Work and Square Root Depth
In this paper we provide a parallel algorithm that given any nnode med...
read it

Efficient Structured Matrix Recovery and NearlyLinear Time Algorithms for Solving Inverse Symmetric MMatrices
In this paper we show how to recover a spectral approximations to broad ...
read it

Towards Optimal Running Times for Optimal Transport
In this work, we provide faster algorithms for approximating the optimal...
read it

PerronFrobenius Theory in Nearly Linear Time: Positive Eigenvectors, Mmatrices, Graph Kernels, and Other Applications
In this paper we provide nearly linear time algorithms for several probl...
read it

Efficient O(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse
In this paper we consider the problem of efficiently computing ϵsketche...
read it
Arun Jambulapati
is this you? claim profile