About

Aaron Sidford is an Associate Professor of Management Science and Engineering and of Computer Science at Stanford University. His research focuses on areas within management science and engineering, with an emphasis on computational methods and algorithms. As a faculty member, he contributes to the academic community through his expertise in these fields, supporting the university's mission of advancing knowledge and education in management science and engineering.

Research topics

• Computer Science
• Mathematics
• Combinatorics
• Algorithm
• Mathematical optimization
• Statistics
• Machine Learning
• Data Mining
• Discrete mathematics
• Theoretical computer science
• Statistical physics
• Physics

Selected publications

• From Incremental Transitive Cover to Strongly Polynomial Maximum Flow

  ArXiv.org · 2025-10-23

  preprintOpen access

  We provide faster strongly polynomial time algorithms solving maximum flow in structured $n$-node $m$-arc networks. Our results imply an $n^{ω+ o(1)}$-time strongly polynomial time algorithms for computing a maximum bipartite $b$-matching where $ω$ is the matrix multiplication constant. Additionally, they imply an $m^{1 + o(1)} W$-time algorithm for solving the problem on graphs with a given tree decomposition of width $W$. We obtain these results by strengthening and efficiently implementing an approach in Orlin's (STOC 2013) state-of-the-art $O(mn)$ time maximum flow algorithm. We develop a general framework that reduces solving maximum flow with arbitrary capacities to (1) solving a sequence of maximum flow problems with polynomial bounded capacities and (2) dynamically maintaining a size-bounded supersets of the transitive closure under arc additions; we call this problem \emph{incremental transitive cover}. Our applications follow by leveraging recent weakly polynomial, almost linear time algorithms for maximum flow due to Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva (FOCS 2022) and Brand, Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva, Sidford (FOCS 2023), and by developing incremental transitive cover data structures.

  PublisherOA PDFDOI

• Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure

  ArXiv.org · 2025-07-15

  preprintOpen accessSenior author

  We provide new high-accuracy randomized algorithms for solving linear systems and regression problems that are well-conditioned except for $k$ large singular values. For solving such $d \times d$ positive definite system our algorithms succeed whp. and run in time $\tilde O(d^2 + k^ω)$. For solving such regression problems in a matrix $\mathbf{A} \in \mathbb{R}^{n \times d}$ our methods succeed whp. and run in time $\tilde O(\mathrm{nnz}(\mathbf{A}) + d^2 + k^ω)$ where $ω$ is the matrix multiplication exponent and $\mathrm{nnz}(\mathbf{A})$ is the number of non-zeros in $\mathbf{A}$. Our methods nearly-match a natural complexity limit under dense inputs for these problems and improve upon a trade-off in prior approaches that obtain running times of either $\tilde O(d^{2.065}+k^ω)$ or $\tilde O(d^2 + dk^{ω-1})$ for $d\times d$ systems. Moreover, we show how to obtain these running times even under the weaker assumption that all but $k$ of the singular values have a suitably bounded generalized mean. Consequently, we give the first nearly-linear time algorithm for computing a multiplicative approximation to the nuclear norm of an arbitrary dense matrix. Our algorithms are built on three general recursive preconditioning frameworks, where matrix sketching and low-rank update formulas are carefully tailored to the problems' structure.

  PublisherOA PDFDOI

• Eulerian Graph Sparsification by Effective Resistance Decomposition

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01 · 1 citations

  book-chapter

  We provide an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an (n log2 n · ∈-2)-edge ε-approximate Eulerian sparsifier with high probability in (m log3 n ) time (where (·) hides polyloglog(n ) factors). Due to a reduction from [Peng-Song, STOC ’22], this yields an (m log3 n + n log6 n )-time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially-bounded weights with high probability, improving upon the previous state- of-the-art runtime of Ω(m log8 n + n log23 n ). We also give a polynomial-time algorithm that computes O (min(n log n · ε-2 + n log5/3 n log3/2 n · ε-2))-edge sparsifiers, improving the best such sparsity bound of O (n log2 n · ε-2 + n log8/3 n · ε-4/3) [Sachdeva-Thudi-Zhao, ICALP ’24].

  PublisherDOI

• Entropy Regularization and Faster Decremental Matching in General Graphs

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01 · 1 citations

  book-chapter

  We provide an algorithm that maintains, against an adaptive adversary, a (1 — ε )-approximate maximum matching in n-node m-edge general (not necessarily bipartite) undirected graph undergoing edge deletions with high probability with (amortized) O (poly(ε-1, log n )) time per update. We also obtain the same update time for maintaining a fractional approximate weighted matching (and hence an approximation to the value of the maximum weight matching) and an integral approximate weighted matching in dense graphs.1 Our unweighted result improves upon the prior state-of-the-art which includes a poly(log n ) · 2O (1/ɛ2) update time [Assadi-Bernstein-Dudeja 2022] and an update time [Gupta-Peng 2013], and our weighted result improves upon the log n ) update time due to [Gupta-Peng 2013].

  PublisherDOI

• Balancing Gradient and Hessian Queries in Non-Convex Optimization

  ArXiv.org · 2025-10-23

  preprintOpen access

  We develop optimization methods which offer new trade-offs between the number of gradient and Hessian computations needed to compute the critical point of a non-convex function. We provide a method that for any twice-differentiable $f\colon \mathbb R^d \rightarrow \mathbb R$ with $L_2$-Lipschitz Hessian, input initial point with $Δ$-bounded sub-optimality, and sufficiently small $ε> 0$, outputs an $ε$-critical point, i.e., a point $x$ such that $\|\nabla f(x)\| \leq ε$, using $\tilde{O}(L_2^{1/4} n_H^{-1/2}Δε^{-9/4})$ queries to a gradient oracle and $n_H$ queries to a Hessian oracle for any positive integer $n_H$. As a consequence, we obtain an improved gradient query complexity of $\tilde{O}(d^{1/3}L_2^{1/2}Δε^{-3/2})$ in the case of bounded dimension and of $\tilde{O}(L_2^{3/4}Δ^{3/2}ε^{-9/4})$ in the case where we are allowed only a \emph{single} Hessian query. We obtain these results through a more general algorithm which can handle approximate Hessian computations and recovers the state-of-the-art bound of computing an $ε$-critical point with $O(L_1^{1/2}L_2^{1/4}Δε^{-7/4})$ gradient queries provided that $f$ also has an $L_1$-Lipschitz gradient.

  PublisherOA PDFDOI

• Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs

  ArXiv.org · 2025-03-31

  preprintOpen accessSenior author

  We provide $m^{1+o(1)}kε^{-1}$-time algorithms for computing multiplicative $(1 - ε)$-approximate solutions to multi-commodity flow problems with $k$-commodities on $m$-edge directed graphs, including concurrent multi-commodity flow and maximum multi-commodity flow. To obtain our results, we provide new optimization tools of potential independent interest. First, we provide an improved optimization method for solving $\ell_{q, p}$-regression problems to high accuracy. This method makes $\tilde{O}_{q, p}(k)$ queries to a high accuracy convex minimization oracle for an individual block, where $\tilde{O}_{q, p}(\cdot)$ hides factors depending only on $q$, $p$, or $\mathrm{poly}(\log m)$, improving upon the $\tilde{O}_{q, p}(k^2)$ bound of [Chen-Ye, ICALP 2024]. As a result, we obtain the first almost-linear time algorithm that solves $\ell_{q, p}$ flows on directed graphs to high accuracy. Second, we present optimization tools to reduce approximately solving composite $\ell_{1, \infty}$-regression problems to solving $m^{o(1)}ε^{-1}$ instances of composite $\ell_{q, p}$-regression problem. The method builds upon recent advances in solving box-simplex games [Jambulapati-Tian, NeurIPS 2023] and the area convex regularizer introduced in [Sherman, STOC 2017] to obtain faster rates for constrained versions of the problem. Carefully combining these techniques yields our directed multi-commodity flow algorithm.

  PublisherOA PDFDOI

• Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs

  2025-06-15 · 1 citations

  articleSenior author
  PublisherDOI

• Improved girth approximation in weighted undirected graphs

  ArXiv.org · 2025-07-18

  preprintOpen access

  Let $G = (V,E,\ell)$ be a $n$-node $m$-edge weighted undirected graph, where $\ell: E \rightarrow (0,\infty)$ is a real \emph{length} function defined on its edges, and let $g$ denote the girth of $G$, i.e., the length of its shortest cycle. We present an algorithm that, for any input, integer $k \geq 1$, in $O(kn^{1+1/k}\log{n} + m(k+\log{n}))$ expected time finds a cycle of length at most $\frac{4k}{3}g$. This algorithm nearly matches a $O(n^{1+1/k}\log{n})$-time algorithm of \cite{KadriaRSWZ22} which applied to unweighted graphs of girth $3$. For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in $O((n^{1+1/k}\log n+m)\log (nM))$ time, where $\ell: E \rightarrow [1, M]$ is an integral length function, finds a cycle of length at most $2kg$~\cite{KadriaRSWZ22}. For $k=1$ this result improves upon the result of Roditty and Tov~\cite{RodittyT13}.

  PublisherOA PDFDOI

• Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization

  arXiv (Cornell University) · 2024-06-11

  preprintOpen access

  We develop a new parallel algorithm for minimizing Lipschitz, convex functions with a stochastic subgradient oracle. The total number of queries made and the query depth, i.e., the number of parallel rounds of queries, match the prior state-of-the-art, [CJJLLST23], while improving upon the computational depth by a polynomial factor for sufficiently small accuracy. When combined with previous state-of-the-art methods our result closes a gap between the best-known query depth and the best-known computational depth of parallel algorithms. Our method starts with a ball acceleration framework of previous parallel methods, i.e., [CJJJLST20, ACJJS21], which reduce the problem to minimizing a regularized Gaussian convolution of the function constrained to Euclidean balls. By developing and leveraging new stability properties of the Hessian of this induced function, we depart from prior parallel algorithms and reduce these ball-constrained optimization problems to stochastic unconstrained quadratic minimization problems. Although we are unable to prove concentration of the asymmetric matrices that we use to approximate this Hessian, we nevertheless develop an efficient parallel method for solving these quadratics. Interestingly, our algorithms can be improved using fast matrix multiplication and use nearly-linear work if the matrix multiplication exponent is 2.

  PublisherOA PDFDOI

• Convex optimization with $p$-norm oracles

  arXiv (Cornell University) · 2024-10-31

  preprintOpen accessSenior author

  In recent years, there have been significant advances in efficiently solving $\ell_s$-regression using linear system solvers and $\ell_2$-regression [Adil-Kyng-Peng-Sachdeva, J. ACM'24]. Would efficient smoothed $\ell_p$-norm solvers lead to even faster rates for solving $\ell_s$-regression when $2 \leq p < s$? In this paper, we give an affirmative answer to this question and show how to solve $\ell_s$-regression using $\tilde{O}(n^{\fracν{1+ν}})$ iterations of solving smoothed $\ell_p$ regression problems, where $ν:= \frac{1}{p} - \frac{1}{s}$. To obtain this result, we provide improved accelerated rates for convex optimization problems when given access to an $\ell_p^s(λ)$-proximal oracle, which, for a point $c$, returns the solution of the regularized problem $\min_{x} f(x) + λ||x-c||_p^s$. Additionally, we show that these rates for the $\ell_p^s(λ)$-proximal oracle are optimal for algorithms that query in the span of the outputs of the oracle, and we further apply our techniques to settings of high-order and quasi-self-concordant optimization.

  PublisherOA PDFDOI

Recent grants

• CAREER: Theory of Fast Graph Optimization

  NSF · $550k · 2019–2025

• Collaborative Research: AF: Medium: Foundations of Structured Optimization

  NSF · $630k · 2020–2025

Frequent coauthors

• Yin Tat Lee

  46 shared

• Yang P. Liu

  Stanford University

  39 shared

• Arun Jambulapati

  University of Washington

  37 shared

• Richard Peng

  University of Waterloo

  20 shared

• Jonathan A. Kelner

  19 shared

• Jan van den Brand

  Georgia Institute of Technology

  17 shared

• Michael B. Cohen

  Amherst College

  15 shared

• John Peebles

  15 shared