Arun Jambulapati

activity

20172025

most citedParallel Reachability in Almost Linear Work and Square Root Depth

11 citations · 58 across the 33 of their papers we have counts for

collaborators

Showing cs.DSShow all

21 papers · 1 filter

cs.DS2025

Radial Isotropic Position via an Implicit Newton's Method

Arun Jambulapati, Jonathan Li, Kevin Tian

Placing a dataset $A = {a_{i}}_{i \in [n]} \subset R^{d}$ in radial isotropic position, i.e., finding an invertible $R \in R^{d \times d}$ such th…

cs.DS2024

Eulerian Graph Sparsification by Effective Resistance Decomposition

Arun Jambulapati, Sushant Sachdeva, Aaron Sidford +2

We provide an algorithm that, given an $n$ -vertex $m$ -edge Eulerian graph with polynomially bounded weights, computes an $O ˘ (n lo g^{2} n \cdot ε^{- 2})$ -edge $\vare…

cs.DS2023

Sparsifying generalized linear models

Arun Jambulapati, James R. Lee, Yang P. Liu +1

We consider the sparsification of sums $F : R^{n} \to R$ where $F (x) = f_{1} (⟨ a_{1}, x ⟩) + \dots + f_{m} (⟨ a_{m}, x ⟩)$ for vectors $a_1,\ldots,a_m \…

cs.DS2023

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

Yair Carmon, Arun Jambulapati, Yujia Jin +1

We design algorithms for minimizing $max_{i \in [n]} f_{i} (x)$ over a $d$ -dimensional Euclidean or simplex domain. When each $f_{i}$ is $1$ -Lipschitz and $1$ -smooth, our method computes…

cs.DS2023

Structured Semidefinite Programming for Recovering Structured Preconditioners

Arun Jambulapati, Jerry Li, Christopher Musco +3

We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental p…

cs.DS2023

Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

Arun Jambulapati, Victor Reis, Kevin Tian

Discrepancy theory provides powerful tools for producing higher-quality objects which "beat the union bound" in fundamental settings throughout combinatorics and computer science.…

cs.DS2023★ 2 cited

Sparsifying sums of norms

Arun Jambulapati, James R. Lee, Yang P. Liu +1

For any norms $N_{1}, \dots, N_{m}$ on $R^{n}$ and $N (x) := N_{1} (x) + \dots + N_{m} (x)$ , we show there is a sparsified norm $N ~ (x) = w_{1} N_{1} (x) + \dots + w_{m} N_{m} (x)$ such that…

cs.DS2022

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

Arun Jambulapati, Yang P. Liu, Aaron Sidford

We present an algorithm that given any $n$ -vertex, $m$ -edge, rank $r$ hypergraph constructs a spectral sparsifier with $O (n ε^{- 2} lo g n lo g r)$ hyperedges in nearly-li…

cs.DS2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Arun Jambulapati, Yujia Jin, Aaron Sidford +1

Box-simplex games are a family of bilinear minimax objectives which encapsulate graph-structured problems such as maximum flow [She17], optimal transport [JST19], and bipartite mat…

cs.DS2021

Improved Iteration Complexities for Overconstrained $p$ -Norm Regression

Arun Jambulapati, Yang P. Liu, Aaron Sidford

In this paper we obtain improved iteration complexities for solving $ℓ_{p}$ regression. We provide methods which given any full-rank $A \in R^{n \times d}$ with…

cs.DS2021★ 7 cited

Robust Regression Revisited: Acceleration and Improved Estimation Rates

Arun Jambulapati, Jerry Li, Tselil Schramm +1

We study fast algorithms for statistical regression problems under the strong contamination model, where the goal is to approximately optimize a generalized linear model (GLM) give…

cs.DS2020

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Arun Jambulapati, Aaron Sidford

In this paper we provide an $O (m (lo g lo g n)^{O (1)} lo g (1/ ε))$ -expected time algorithm for solving Laplacian systems on $n$ -node $m$ -edge graphs, improving improving upon the pr…

cs.DS2020

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space

Sepehr Assadi, Arun Jambulapati, Yujia Jin +2

We provide $O (ε^{- 1})$ -pass semi-streaming algorithms for computing $(1 - ε)$ -approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods ar…

cs.DS2020★ 7 cited

Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing

Arun Jambulapati, Jerry Li, Kevin Tian

We develop two methods for the following fundamental statistical task: given an $ε$ -corrupted set of $n$ samples from a $d$ -dimensional sub-Gaussian distribution, return an approxi…

cs.DS2020

Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent

Arun Jambulapati, Yin Tat Lee, Jerry Li +2

We give the first approximation algorithm for mixed packing and covering semidefinite programs (SDPs) with polylogarithmic dependence on width. Mixed packing and covering SDPs cons…

cs.DS2019★ 1 cited

A Direct $O ~ (1/ ε)$ Iteration Parallel Algorithm for Optimal Transport

Arun Jambulapati, Aaron Sidford, Kevin Tian

Optimal transportation, or computing the Wasserstein or ``earth mover's'' distance between two distributions, is a fundamental primitive which arises in many learning and statistic…

cs.DS2019★ 11 cited

Parallel Reachability in Almost Linear Work and Square Root Depth

Arun Jambulapati, Yang P. Liu, Aaron Sidford

In this paper we provide a parallel algorithm that given any $n$ -node $m$ -edge directed graph and source vertex $s$ computes all vertices reachable from $s$ with $O ~ (m)$ wor…

cs.DS2018★ 5 cited

Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$ -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…

cs.DS2018

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…

cs.DS2018★ 4 cited

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 Δ^…

cs.DS2017

Efficient $O (n / ε)$ Spectral Sketches for the Laplacian and its Pseudoinverse

Arun Jambulapati, Aaron Sidford

In this paper we consider the problem of efficiently computing $ε$ -sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance $ε$ , we seek to constr…

Radial Isotropic Position via an Implicit Newton's Method

Eulerian Graph Sparsification by Effective Resistance Decomposition

Sparsifying generalized linear models

A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

Structured Semidefinite Programming for Recovering Structured Preconditioners

Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

Sparsifying sums of norms

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching

Improved Iteration Complexities for Overconstrained p-Norm Regression

Robust Regression Revisited: Acceleration and Improved Estimation Rates

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space

Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing

Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent

A Direct O~(1/ε) Iteration Parallel Algorithm for Optimal Transport

Parallel Reachability in Almost Linear Work and Square Root Depth

Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices

Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications

Towards Optimal Running Times for Optimal Transport

Efficient O(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse

Improved Iteration Complexities for Overconstrained $p$ -Norm Regression

A Direct $O ~ (1/ ε)$ Iteration Parallel Algorithm for Optimal Transport

Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$ -Matrices

Efficient $O (n / ε)$ Spectral Sketches for the Laplacian and its Pseudoinverse