Aaron Sidford

activity

20152025

most citedUn-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

67 citations · 172 across the 19 of their papers we have counts for

collaborators

Showing cs.DSShow all

28 papers · 1 filter

cs.DS2025

Improved girth approximation in weighted undirected graphs

Avi Kadria, Liam Roditty, Aaron Sidford +2

Let $G = (V, E, ℓ)$ be a $n$ -node $m$ -edge weighted undirected graph, where $ℓ : E \to (0, \infty)$ is a real \emph{length} function defined on its edges, and let $g$ den…

cs.DS2021

Computing Lewis Weights to High Precision

Maryam Fazel, Yin Tat Lee, Swati Padmanabhan +1

We present an algorithm for computing approximate $ℓ_{p}$ Lewis weights to high precision. Given a full-rank $A \in R^{m \times n}$ with $m \geq n$ and a scalar…

cs.DS2020

Instance Based Approximations to Profile Maximum Likelihood

Nima Anari, Moses Charikar, Kirankumar Shiragur +1

In this paper we provide a new efficient algorithm for approximately computing the profile maximum likelihood (PML) distribution, a prominent quantity in symmetric property estimat…

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★ 1 cited

Coordinate Methods for Matrix Games

Yair Carmon, Yujia Jin, Aaron Sidford +1

We develop primal-dual coordinate methods for solving bilinear saddle-point problems of the form $min_{x \in X} max_{y \in Y} y^{⊤} A x$ which contain linear p…

cs.DS2020★ 24 cited

Faster Divergence Maximization for Faster Maximum Flow

Yang P. Liu, Aaron Sidford

In this paper we provide an algorithm which given any $m$ -edge $n$ -vertex directed graph with integer capacities at most $U$ computes a maximum $s$ - $t$ flow for any vertices $s$ an…