Aaron Sidford

ORCID

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 207

Top Venues

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm. CoRR (2024)
Jose H. Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford
Towards optimal running timesfor optimal transport. Oper. Res. Lett. 52 (2024)
Yujia Jin, Ishani Karmarkar, Aaron Sidford, Jiayi Wang
Truncated Variance Reduced Value Iteration. CoRR (2024)
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
Sparsifying Generalized Linear Models. STOC (2024)
Arun Jambulapati, Aaron Sidford, Kevin Tian
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization. COLT (2024)
Arun Jambulapati, Aaron Sidford, Kevin Tian
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization. CoRR (2024)
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. STOC (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. SODA (2024)
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions. SODA (2024)
Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract). COLT (2024)
Simon Apers, Sander Gribling, Aaron Sidford
On computing approximate Lewis weights. CoRR (2024)
Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, Kevin Tian
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling. CoRR (2023)
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
Towards Optimal Effective Resistance Estimation. CoRR (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. CoRR (2023)
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
Sparsifying generalized linear models. CoRR (2023)
Jonathan A. Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian
Semi-Random Sparse Recovery in Nearly-Linear Time. COLT (2023)
Aaron Sidford, Chenyi Zhang
Quantum speedups for stochastic optimization. NeurIPS (2023)
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs. CoRR (2023)
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
Moments, Random Walks, and Limits for Spectrum Approximation. CoRR (2023)
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
Improved girth approximation in weighted undirected graphs. SODA (2023)
Andrei Graur, Haotian Jiang, Aaron Sidford
Sparse Submodular Function Minimization. FOCS (2023)
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian
ReSQueing Parallel and Private Stochastic Convex Optimization. CoRR (2023)
Jan Van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. FOCS (2023)
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
Matrix Completion in Almost-Verification Time. CoRR (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. CoRR (2023)
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs. FOCS (2023)
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification. CoRR (2023)
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract). IJCAI (2023)
Andrei Graur, Haotian Jiang, Aaron Sidford
Sparse Submodular Function Minimization. CoRR (2023)
Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, Kevin Tian
Structured Semidefinite Programming for Recovering Structured Preconditioners. CoRR (2023)
Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, Kevin Tian
Structured Semidefinite Programming for Recovering Structured Preconditioners. NeurIPS (2023)
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
Parallel Submodular Function Minimization. NeurIPS (2023)
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
Moments, Random Walks, and Limits for Spectrum Approximation. COLT (2023)
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions. CoRR (2023)
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
Sparsifying Sums of Norms. CoRR (2023)
Jan van den Brand, Yang P. Liu, Aaron Sidford
Dynamic Maxflow via Dynamic Interior Point Methods. STOC (2023)
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
Parallel Submodular Function Minimization. CoRR (2023)
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
Sparsifying Sums of Norms. FOCS (2023)
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian
ReSQueing Parallel and Private Stochastic Convex Optimization. FOCS (2023)
Jiale Chen, Aaron Sidford, Ta-Wei Tu
Entropy Regularization and Faster Decremental Matching in General Graphs. CoRR (2023)
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
Matrix Completion in Almost-Verification Time. FOCS (2023)
Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, Kevin Tian
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling. ICML (2023)
Arun Jambulapati, Yang P. Liu, Aaron Sidford
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification. STOC (2023)
Aaron Sidford, Chenyi Zhang
Quantum speedups for stochastic optimization. CoRR (2023)
Yujia Jin, Vidya Muthukumar, Aaron Sidford
The Complexity of Infinite-Horizon General-Sum Stochastic Games. ITCS (2023)
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
Towards Optimal Effective Resistance Estimation. NeurIPS (2023)
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
Efficient Convex Optimization Requires Superlinear Memory. CoRR (2022)
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood. NeurIPS (2022)
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford
Computing Lewis Weights to High Precision. SODA (2022)
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, Aaron Sidford
Optimal and Adaptive Monteiro-Svaiter Acceleration. CoRR (2022)
Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space. SODA (2022)
Yujia Jin, Aaron Sidford, Kevin Tian
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods. CoRR (2022)
Arun Jambulapati, Yang P. Liu, Aaron Sidford
-norm regression. STOC (2022)
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization. CoRR (2022)
Arun Jambulapati, Yang P. Liu, Aaron Sidford
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification. CoRR (2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. ICALP (2022)
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, Aaron Sidford
Optimal and Adaptive Monteiro-Svaiter Acceleration. NeurIPS (2022)
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
Improved Lower Bounds for Submodular Function Minimization. FOCS (2022)
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
Efficient Convex Optimization Requires Superlinear Memory. COLT (2022)
Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. ICALP (2022)
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford
Faster maxflow via improved dynamic spectral vertex sparsifiers. STOC (2022)
Jan van den Brand, Yang P. Liu, Aaron Sidford
Dynamic Maxflow via Dynamic Interior Point Methods. CoRR (2022)
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
Algorithmic trade-offs for girth approximation in undirected graphs. SODA (2022)
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization. ICML (2022)
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood. CoRR (2022)
Yujia Jin, Vidya Muthukumar, Aaron Sidford
The Complexity of Infinite-Horizon General-Sum Stochastic Games. CoRR (2022)
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
Improved Lower Bounds for Submodular Function Minimization. CoRR (2022)
Yujia Jin, Aaron Sidford, Kevin Tian
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods. COLT (2022)
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. COLT (2022)
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
Semi-Random Sparse Recovery in Nearly-Linear Time. CoRR (2022)
Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching. CoRR (2022)
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford
Computing Lewis Weights to High Precision. CoRR (2021)
Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
Stochastic Bias-Reduced Gradient Methods. CoRR (2021)
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
Lower bounds for finding stationary points II: first-order methods. Math. Program. 185 (1-2) (2021)
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. SIAM J. Comput. 50 (6) (2021)
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
-Regression in Nearly Linear Time for Dense Instances. CoRR (2021)
Arun Jambulapati, Aaron Sidford
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. SODA (2021)
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
-regression in nearly linear time for dense instances. STOC (2021)
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss. COLT (2021)
Arun Jambulapati, Yang P. Liu, Aaron Sidford
Improved Iteration Complexities for Overconstrained p-Norm Regression. CoRR (2021)
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood. COLT (2021)
Michael B. Cohen, Aaron Sidford, Kevin Tian
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. ITCS (2021)
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. CoRR (2021)
Yujia Jin, Aaron Sidford
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs. ICML (2021)
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers. CoRR (2021)
Yujia Jin, Aaron Sidford
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs. CoRR (2021)
Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
Stochastic Bias-Reduced Gradient Methods. NeurIPS (2021)
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss. CoRR (2021)
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
Deterministic Approximation of Random Walks in Small Space. Theory Comput. 17 (2021)
Tarun Kathuria, Yang P. Liu, Aaron Sidford
Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time. FOCS (2020)
Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song
Solving tall dense linear programs in nearly linear time. STOC (2020)
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian
Acceleration with a Ball Optimization Oracle. NeurIPS (2020)
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. CoRR (2020)
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
Coordinate Methods for Matrix Games. FOCS (2020)
Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos
Fast and Space Efficient Spectral Sparsification in Dynamic Streams. SODA (2020)
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
Instance Based Approximations to Profile Maximum Likelihood. NeurIPS (2020)
Yang P. Liu, Aaron Sidford
Faster Divergence Maximization for Faster Maximum Flow. CoRR (2020)
Daniel Levy, Yair Carmon, John C. Duchi, Aaron Sidford
Large-Scale Methods for Distributionally Robust Optimization. CoRR (2020)
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
Coordinate Methods for Matrix Games. CoRR (2020)
Oliver Hinder, Aaron Sidford, Nimit Sharad Sohoni
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond. COLT (2020)

Aaron Sidford.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Aaron Sidford