Aaron Sidford

259 papers A* 110A 6B 2Journal 138Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A* conf
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure.
SODA
Michal Derezinski, Aaron Sidford
2026 A* conf
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow.
SODA
Daniel Dadush, James B. Orlin, Aaron Sidford, László A. Végh
2026 J jnl
Solving Matrix Games with Near-Optimal Matvec Complexity.
CoRR
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
2025 J jnl
Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs.
CoRR
Li Chen, Andrei Graur, Aaron Sidford
2025 A* conf
Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs.
STOC
Li Chen, Andrei Graur, Aaron Sidford
2025 J jnl
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure.
CoRR
Michal Derezinski, Aaron Sidford
2025 J jnl
Balancing Gradient and Hessian Queries in Non-Convex Optimization.
CoRR
Deeksha Adil, Brian Bullins, Aaron Sidford, Chenyi Zhang
2025 A* conf
Entropy Regularization and Faster Decremental Matching in General Graphs.
SODA
Jiale Chen, Aaron Sidford, Ta-Wei Tu
2025 A* conf
Eulerian Graph Sparsification by Effective Resistance Decomposition.
SODA
Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, Yibin Zhao
2025 A conf
Extracting Dual Solutions via Primal Optimizers.
ITCS
Yair Carmon, Arun Jambulapati, Liam O'Carroll, Aaron Sidford
2025 J jnl
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow.
CoRR
Daniel Dadush, James B. Orlin, Aaron Sidford, László A. Végh
2025 A* conf
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs.
FOCS
Shunhua Jiang, Michael Kapralov, Lawrence Li, Aaron Sidford
2025 J jnl
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs.
CoRR
Shunhua Jiang, Michael Kapralov, Lawrence Li, Aaron Sidford
2025 J jnl
Improved girth approximation in weighted undirected graphs.
CoRR
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
2025 J jnl
Isotropic Noise in Stochastic and Quantum Convex Optimization.
CoRR
Annie Marsden, Liam O'Carroll, Aaron Sidford, Chenyi Zhang
2025 A* conf
Matching Composition and Efficient Weight Reduction in Dynamic Matching.
SODA
Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu
2025 J jnl
Reusing Samples in Variance Reduction.
CoRR
Yujia Jin, Ishani Karmarkar, Aaron Sidford, Jiayi Wang
2025 A* conf
Solving Zero-Sum Games with Fewer Matrix-Vector Products.
FOCS
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
2025 J jnl
Solving Zero-Sum Games with Fewer Matrix-Vector Products.
CoRR
Ishani Karmarkar, Liam O'Carroll, Aaron Sidford
2025 J jnl
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers.
ACM Trans. Algorithms
Arun Jambulapati, Aaron Sidford
2024 A* conf
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions.
SODA
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2024 A* conf
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization.
COLT
Arun Jambulapati, Aaron Sidford, Kevin Tian
2024 J jnl
Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization.
CoRR
Arun Jambulapati, Aaron Sidford, Kevin Tian
2024 J jnl
Convex optimization with
CoRR
Deeksha Adil, Brian Bullins, Arun Jambulapati, Aaron Sidford
2024 J jnl
Efficient Convex Optimization Requires Superlinear Memory.
J. ACM
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
2024 J jnl
Eulerian Graph Sparsification by Effective Resistance Decomposition.
CoRR
Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, Yibin Zhao
2024 J jnl
Extracting Dual Solutions via Primal Optimizers.
CoRR
Yair Carmon, Arun Jambulapati, Liam O'Carroll, Aaron Sidford
2024 A* conf
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract).
COLT
Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
2024 J jnl
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm.
CoRR
Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
2024 A* conf
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.
SODA
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2024 J jnl
Matching Composition and Efficient Weight Reduction in Dynamic Matching.
CoRR
Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, Ta-Wei Tu
2024 A* conf
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
STOC
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
2024 J jnl
On computing approximate Lewis weights.
CoRR
Simon Apers, Sander Gribling, Aaron Sidford
2024 A* conf
Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting.
NeurIPS
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
2024 A* conf
Sparsifying Generalized Linear Models.
STOC
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
2024 J jnl
Towards optimal running timesfor optimal transport.
Oper. Res. Lett.
Jose H. Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford
2024 A* conf
Truncated Variance Reduced Value Iteration.
NeurIPS
Yujia Jin, Ishani Karmarkar, Aaron Sidford, Jiayi Wang
2024 J jnl
Truncated Variance Reduced Value Iteration.
CoRR
Yujia Jin, Ishani Karmarkar, Aaron Sidford, Jiayi Wang
2024 J jnl
Unit Capacity Maxflow in Almost $m^{4/3}$ Time.
SIAM J. Comput.
Tarun Kathuria, Yang P. Liu, Aaron Sidford
2023 A* conf
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
FOCS
Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2023 J jnl
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
CoRR
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2023 J jnl
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions.
CoRR
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2023 A* conf
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.
STOC
Arun Jambulapati, Yang P. Liu, Aaron Sidford
2023 A* conf
Dynamic Maxflow via Dynamic Interior Point Methods.
STOC
Jan van den Brand, Yang P. Liu, Aaron Sidford
2023 A* conf
Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract).
IJCAI
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
2023 J jnl
Entropy Regularization and Faster Decremental Matching in General Graphs.
CoRR
Jiale Chen, Aaron Sidford, Ta-Wei Tu
2023 A* conf
Improved girth approximation in weighted undirected graphs.
SODA
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
2023 J jnl
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.
CoRR
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2023 A* conf
Matrix Completion in Almost-Verification Time.
FOCS
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
2023 J jnl
Matrix Completion in Almost-Verification Time.
CoRR
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
2023 A* conf
Moments, Random Walks, and Limits for Spectrum Approximation.
COLT
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
2023 J jnl
Moments, Random Walks, and Limits for Spectrum Approximation.
CoRR
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh
2023 J jnl
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.
CoRR
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
2023 A* conf
Parallel Submodular Function Minimization.
NeurIPS
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
2023 J jnl
Parallel Submodular Function Minimization.
CoRR
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
2023 A* conf
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.
ICML
Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, Kevin Tian
2023 J jnl
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.
CoRR
Adam Bouland, Yosheb Getachew, Yujia Jin, Aaron Sidford, Kevin Tian
2023 A* conf
Quantum speedups for stochastic optimization.
NeurIPS
Aaron Sidford, Chenyi Zhang
2023 J jnl
Quantum speedups for stochastic optimization.
CoRR
Aaron Sidford, Chenyi Zhang
2023 A* conf
ReSQueing Parallel and Private Stochastic Convex Optimization.
FOCS
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian
2023 J jnl
ReSQueing Parallel and Private Stochastic Convex Optimization.
CoRR
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian
2023 A* conf
Semi-Random Sparse Recovery in Nearly-Linear Time.
COLT
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
2023 J jnl
Singular Value Approximation and Reducing Directed to Undirected Graph Sparsification.
CoRR
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
2023 A* conf
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.
FOCS
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan
2023 A* conf
Sparse Submodular Function Minimization.
FOCS
Andrei Graur, Haotian Jiang, Aaron Sidford
2023 J jnl
Sparse Submodular Function Minimization.
CoRR
Andrei Graur, Haotian Jiang, Aaron Sidford
2023 A* conf
Sparsifying Sums of Norms.
FOCS
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
2023 J jnl
Sparsifying Sums of Norms.
CoRR
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
2023 J jnl
Sparsifying generalized linear models.
CoRR
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
2023 A* conf
Structured Semidefinite Programming for Recovering Structured Preconditioners.
NeurIPS
Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, Kevin Tian
2023 J jnl
Structured Semidefinite Programming for Recovering Structured Preconditioners.
CoRR
Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur, Aaron Sidford, Kevin Tian
2023 A conf
The Complexity of Infinite-Horizon General-Sum Stochastic Games.
ITCS
Yujia Jin, Vidya Muthukumar, Aaron Sidford
2023 A* conf
Towards Optimal Effective Resistance Estimation.
NeurIPS
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
2023 J jnl
Towards Optimal Effective Resistance Estimation.
CoRR
Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
2022 A* conf
Algorithmic trade-offs for girth approximation in undirected graphs.
SODA
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick
2022 A* conf
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales.
COLT
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan
2022 J jnl
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.
CoRR
Arun Jambulapati, Yang P. Liu, Aaron Sidford
2022 A* conf
Computing Lewis Weights to High Precision.
SODA
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford
2022 J jnl
Dynamic Maxflow via Dynamic Interior Point Methods.
CoRR
Jan van den Brand, Yang P. Liu, Aaron Sidford
2022 A* conf
Efficient Convex Optimization Requires Superlinear Memory.
COLT
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
2022 J jnl
Efficient Convex Optimization Requires Superlinear Memory.
CoRR
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant
2022 A* conf
Faster maxflow via improved dynamic spectral vertex sparsifiers.
STOC
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford
2022 A* conf
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
ICALP
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2022 A* conf
Improved Lower Bounds for Submodular Function Minimization.
FOCS
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
2022 J jnl
Improved Lower Bounds for Submodular Function Minimization.
CoRR
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford
2022 A* conf
Improved iteration complexities for overconstrained
STOC
Arun Jambulapati, Yang P. Liu, Aaron Sidford
2022 A* conf
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood.
NeurIPS
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
2022 J jnl
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood.
CoRR
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford
2022 A* conf
Optimal and Adaptive Monteiro-Svaiter Acceleration.
NeurIPS
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, Aaron Sidford
2022 J jnl
Optimal and Adaptive Monteiro-Svaiter Acceleration.
CoRR
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, Aaron Sidford
2022 A* conf
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization.
ICML
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2022 J jnl
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization.
CoRR
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2022 A* conf
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching.
ICALP
Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
2022 J jnl
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching.
CoRR
Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
2022 J jnl
Semi-Random Sparse Recovery in Nearly-Linear Time.
CoRR
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
2022 A* conf
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space.
SODA
Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian
2022 A* conf
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods.
COLT
Yujia Jin, Aaron Sidford, Kevin Tian
2022 J jnl
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods.
CoRR
Yujia Jin, Aaron Sidford, Kevin Tian
2022 J jnl
The Complexity of Infinite-Horizon General-Sum Stochastic Games.
CoRR
Yujia Jin, Vidya Muthukumar, Aaron Sidford
2021 J jnl
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales.
CoRR
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan
2021 J jnl
Computing Lewis Weights to High Precision.
CoRR
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford
2021 J jnl
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
SIAM J. Comput.
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
2021 J jnl
Deterministic Approximation of Random Walks in Small Space.
Theory Comput.
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
2021 J jnl
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers.
CoRR
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford
2021 J jnl
Improved Iteration Complexities for Overconstrained p-Norm Regression.
CoRR
Arun Jambulapati, Yang P. Liu, Aaron Sidford
2021 J jnl
Lower bounds for finding stationary points II: first-order methods.
Math. Program.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
2021 J jnl
Minimum Cost Flows, MDPs, and 𝓁
CoRR
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2021 A* conf
Minimum cost flows, MDPs, and ℓ
STOC
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2021 A conf
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.
ITCS
Michael B. Cohen, Aaron Sidford, Kevin Tian
2021 A* conf
Stochastic Bias-Reduced Gradient Methods.
NeurIPS
Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2021 J jnl
Stochastic Bias-Reduced Gradient Methods.
CoRR
Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2021 A* conf
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood.
COLT
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2021 A* conf
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss.
COLT
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2021 J jnl
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss.
CoRR
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford
2021 A* conf
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs.
ICML
Yujia Jin, Aaron Sidford
2021 J jnl
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs.
CoRR
Yujia Jin, Aaron Sidford
2021 A* conf
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers.
SODA
Arun Jambulapati, Aaron Sidford
2020 J jnl
A General Framework for Symmetric Property Estimation.
CoRR
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020 A* conf
Acceleration with a Ball Optimization Oracle.
NeurIPS
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian
2020 J jnl
Acceleration with a Ball Optimization Oracle.
CoRR
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian
2020 A* conf
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
FOCS
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020 J jnl
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
CoRR
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
2020 A* conf
Constant girth approximation for directed graphs in subquadratic time.
STOC
Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
2020 A* conf
Coordinate Methods for Matrix Games.
FOCS
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
2020 J jnl
Coordinate Methods for Matrix Games.
CoRR
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
2020 A* conf
Efficiently Solving MDPs with Stochastic Mirror Descent.
ICML
Yujia Jin, Aaron Sidford
2020 J jnl
Efficiently Solving MDPs with Stochastic Mirror Descent.
CoRR
Yujia Jin, Aaron Sidford
2020 A* conf
Fast and Space Efficient Spectral Sparsification in Dynamic Streams.
SODA
Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos
2020 J jnl
Faster Divergence Maximization for Faster Maximum Flow.
CoRR
Yang P. Liu, Aaron Sidford
2020 A* conf
Faster energy maximization for faster maximum flow.
STOC
Yang P. Liu, Aaron Sidford
2020 J jnl
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
CoRR
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2020 A* conf
High-precision Estimation of Random Walks in Small Space.
FOCS
AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan
2020 A* conf
Instance Based Approximations to Profile Maximum Likelihood.
NeurIPS
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020 J jnl
Instance Based Approximations to Profile Maximum Likelihood.
CoRR
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020 A* conf
Large-Scale Methods for Distributionally Robust Optimization.
NeurIPS
Daniel Levy, Yair Carmon, John C. Duchi, Aaron Sidford
2020 J jnl
Large-Scale Methods for Distributionally Robust Optimization.
CoRR
Daniel Levy, Yair Carmon, John C. Duchi, Aaron Sidford
2020 B conf
Leverage Score Sampling for Faster Accelerated Regression and ERM.
ALT
Naman Agarwal, Sham M. Kakade, Rahul Kidambi, Yin Tat Lee, Praneeth Netrapalli, Aaron Sidford
2020 J jnl
Lower bounds for finding stationary points I.
Math. Program.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
2020 A* conf
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.
COLT
Oliver Hinder, Aaron Sidford, Nimit Sharad Sohoni
2020 A* conf
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization.
SODA
Brian Axelrod, Yang P. Liu, Aaron Sidford
2020 J jnl
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.
CoRR
Michael B. Cohen, Aaron Sidford, Kevin Tian
2020 J jnl
Semi-Streaming Bipartite Matching in Fewer Passes and Less Space.
CoRR
Yujia Jin, Aaron Sidford, Kevin Tian
2020 A conf
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.
AISTATS
Aaron Sidford, Mengdi Wang, Lin Yang, Yinyu Ye
2020 J jnl
Solving Tall Dense Linear Programs in Nearly Linear Time.
CoRR
Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song
2020 A* conf
Solving tall dense linear programs in nearly linear time.
STOC
Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song
2020 J jnl
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood.
CoRR
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2020 J jnl
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers.
CoRR
Arun Jambulapati, Aaron Sidford
2020 A* conf
Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time.
FOCS
Tarun Kathuria, Yang P. Liu, Aaron Sidford
2020 J jnl
Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise.
CoRR
Jerry Li, Aaron Sidford, Kevin Tian, Huishuai Zhang
2019 J jnl
A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport.
CoRR
Arun Jambulapati, Aaron Sidford, Kevin Tian
2019 A* conf
A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport.
NeurIPS
Arun Jambulapati, Aaron Sidford, Kevin Tian
2019 A* conf
A General Framework for Symmetric Property Estimation.
NeurIPS
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2019 A* conf
A Rank-1 Sketch for Matrix Multiplicative Weights.
COLT
Yair Carmon, John C. Duchi, Aaron Sidford, Kevin Tian
2019 J jnl
A Rank-1 Sketch for Matrix Multiplicative Weights.
CoRR
Yair Carmon, John C. Duchi, Aaron Sidford, Kevin Tian
2019 A* conf
Complexity of Highly Parallel Non-Smooth Convex Optimization.
NeurIPS
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford
2019 J jnl
Complexity of Highly Parallel Non-Smooth Convex Optimization.
CoRR
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford
2019 — conf
Deterministic Approximation of Random Walks in Small Space.
APPROX-RANDOM
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
2019 J jnl
Deterministic Approximation of Random Walks in Small Space.
CoRR
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
2019 J jnl
Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space.
CoRR
Michael Kapralov, Navid Nouri, Aaron Sidford, Jakab Tardos
2019 J jnl
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation.
CoRR
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2019 A* conf
Efficient profile maximum likelihood for universal symmetric property estimation.
STOC
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
2019 J jnl
Faster Energy Maximization for Faster Maximum Flow.
CoRR
Yang P. Liu, Aaron Sidford
2019 A* conf
Faster Matroid Intersection.
FOCS
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong
2019 J jnl
Faster Matroid Intersection.
CoRR
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong
2019 J jnl
High-precision Estimation of Random Walks in Small Space.
CoRR
AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan
2019 J jnl
Improved Girth Approximation and Roundtrip Spanners.
CoRR
Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
2019 J jnl
Memory-Sample Tradeoffs for Linear Regression with Small Error.
CoRR
Vatsal Sharan, Aaron Sidford, Gregory Valiant
2019 A* conf
Memory-sample tradeoffs for linear regression with small error.
STOC
Vatsal Sharan, Aaron Sidford, Gregory Valiant
2019 A* conf
Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.
COLT
Alexander V. Gasnikov, Pavel E. Dvurechensky, Eduard Gorbunov, Evgeniya A. Vorontsova, Daniil Selikhanovych, César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford
2019 J jnl
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.
CoRR
Oliver Hinder, Aaron Sidford, Nimit Sharad Sohoni
2019 J jnl
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization.
CoRR
Brian Axelrod, Yang P. Liu, Aaron Sidford
2019 A* conf
Near-optimal method for highly smooth convex optimization.
COLT
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford
2019 A* conf
Parallel Reachability in Almost Linear Work and Square Root Depth.
FOCS
Yang P. Liu, Arun Jambulapati, Aaron Sidford
2019 J jnl
Parallel Reachability in Almost Linear Work and Square Root Depth.
CoRR
Arun Jambulapati, Yang P. Liu, Aaron Sidford
2019 A* conf
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications.
SODA
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford
2019 A* conf
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG.
NeurIPS
Yujia Jin, Aaron Sidford
2019 J jnl
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG.
CoRR
Yujia Jin, Aaron Sidford
2019 J jnl
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.
CoRR
Aaron Sidford, Mengdi Wang, Lin F. Yang, Yinyu Ye
2019 J jnl
Solving Linear Programs with Sqrt(rank) Linear System Solves.
CoRR
Yin Tat Lee, Aaron Sidford
2019 A* conf
Variance Reduction for Matrix Games.
NeurIPS
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
2019 J jnl
Variance Reduction for Matrix Games.
CoRR
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian
2018 J jnl
Accelerated Methods for NonConvex Optimization.
SIAM J. Optim.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
2018 A* conf
Accelerating Stochastic Gradient Descent for Least Squares Regression.
COLT
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford
2018 A* conf
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.
SODA
Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams
2018 A* conf
Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow.
FOCS
Aaron Sidford, Kevin Tian
2018 J jnl
Coordinate Methods for Accelerating 𝓁
CoRR
Aaron Sidford, Kevin Tian
2018 A* conf
Efficient
SODA
Arun Jambulapati, Aaron Sidford
2018 A* conf
Efficient Convex Optimization with Membership Oracles.
COLT
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
2018 J jnl
Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric M-Matrices.
CoRR
Arun Jambulapati, Kirankumar Shiragur, Aaron Sidford
2018 A* conf
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression.
NeurIPS
Neha Gupta, Aaron Sidford
2018 J jnl
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression.
CoRR
Neha Gupta, Aaron Sidford
2018 A* conf
Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model.
NeurIPS
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, Yinyu Ye
2018 J jnl
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications.
CoRR
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford
2018 A* conf
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations.
FOCS
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
2018 J jnl
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations.
CoRR
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford
2018 A conf
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
ITCS
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff
2018 A* conf
Stability of the Lanczos Method for Matrix Function Approximation.
SODA
Cameron Musco, Christopher Musco, Aaron Sidford
2018 J jnl
Towards Optimal Running Times for Optimal Transport.
CoRR
Jose H. Blanchet, Arun Jambulapati, Carson Kent, Aaron Sidford
2018 A* conf
Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes.
SODA
Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye
2017 A* conf
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions.
ICML
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
2017 — conf
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares).
FSTTCS
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, Aaron Sidford
2017 J jnl
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares).
CoRR
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, Aaron Sidford
2017 J jnl
Accelerating Stochastic Gradient Descent.
CoRR
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford
2017 A* conf
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs.
STOC
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
2017 J jnl
Arboral satisfaction: Recognition and LP approximation.
Inf. Process. Lett.
Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler
2017 A* conf
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
FOCS
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
2017 J jnl
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
CoRR
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan
2017 J jnl
Efficient Convex Optimization with Membership Oracles.
CoRR
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
2017 J jnl
Efficient Õ(n/ε) Spectral Sketches for the Laplacian and its Pseudoinverse.
CoRR
Arun Jambulapati, Aaron Sidford
2017 J jnl
Leverage Score Sampling for Faster Accelerated Regression and ERM.
CoRR
Naman Agarwal, Sham M. Kakade, Rahul Kidambi, Yin Tat Lee, Praneeth Netrapalli, Aaron Sidford
2017 J jnl
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification.
J. Mach. Learn. Res.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford
2017 J jnl
Single Pass Spectral Sparsification in Dynamic Streams.
SIAM J. Comput.
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford
2017 J jnl
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
CoRR
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff
2017 J jnl
Stability of the Lanczos Method for Matrix Function Approximation.
CoRR
Cameron Musco, Christopher Musco, Aaron Sidford
2017 A* conf
Subquadratic submodular function minimization.
STOC
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
2017 J jnl
Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes.
CoRR
Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye
2016 J jnl
Accelerated Methods for Non-Convex Optimization.
CoRR
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
2016 J jnl
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs.
CoRR
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu
2016 J jnl
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.
CoRR
Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams
2016 A* conf
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis.
ICML
Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford
2016 J jnl
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis.
CoRR
Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford
2016 A* conf
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More.
FOCS
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
2016 J jnl
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More.
CoRR
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu
2016 A* conf
Faster Eigenvector Computation via Shift-and-Invert Preconditioning.
ICML
Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford
2016 J jnl
Faster Eigenvector Computation via Shift-and-Invert Preconditioning.
CoRR
Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford
2016 J jnl
Geometric Median in Nearly Linear Time.
CoRR
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford
2016 A* conf
Geometric median in nearly linear time.
STOC
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford
2016 J jnl
Matching Matrix Bernstein with Little Memory: Near-Optimal Finite Sample Guarantees for Oja's Algorithm.
CoRR
Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford
2016 J jnl
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging.
CoRR
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford
2016 A* conf
Principal Component Projection Without Principal Component Analysis.
ICML
Roy Frostig, Cameron Musco, Christopher Musco, Aaron Sidford
2016 J jnl
Principal Component Projection Without Principal Component Analysis.
CoRR
Roy Frostig, Cameron Musco, Christopher Musco, Aaron Sidford
2016 J jnl
Routing under Balance.
CoRR
Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford
2016 A* conf
Routing under balance.
STOC
Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford
2016 A* conf
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm.
COLT
Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford
2016 J jnl
Subquadratic Submodular Function Minimization.
CoRR
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
2015 A* conf
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.
FOCS
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
2015 J jnl
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.
CoRR
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong
2015 A* conf
Competing with the Empirical Risk Minimizer in a Single Pass.
COLT
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford
2015 A* conf
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.
FOCS
Yin Tat Lee, Aaron Sidford
2015 J jnl
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.
CoRR
Yin Tat Lee, Aaron Sidford
2015 — —
Iterative methods, combinatorial optimization, and linear programming beyond the universal barrier.
Aaron Sidford
2015 B conf
Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing.
WADS
Erik D. Demaine, Tim Kaler, Quanquan C. Liu, Aaron Sidford, Adam Yedidia
2015 J jnl
Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation.
CoRR
Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford
2015 A* conf
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization.
ICML
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford
2015 J jnl
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization.
CoRR
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford
2015 A conf
Uniform Sampling for Matrix Approximation.
ITCS
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford
2014 A* conf
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.
SODA
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford
2014 J jnl
Competing with the Empirical Risk Minimizer in a Single Pass.
CoRR
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford
2014 A* conf
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow.
FOCS
Yin Tat Lee, Aaron Sidford
2014 A* conf
Single Pass Spectral Sparsification in Dynamic Streams.
FOCS
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford
2014 J jnl
Single Pass Spectral Sparsification in Dynamic Streams.
CoRR
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford
2014 J jnl
Uniform Sampling for Matrix Approximation.
CoRR
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford
2013 J jnl
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
CoRR
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu
2013 A* conf
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.
STOC
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu
2013 J jnl
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
CoRR
Jonathan A. Kelner, Lorenzo Orecchia, Yin Tat Lee, Aaron Sidford
2013 J jnl
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
CoRR
Yin Tat Lee, Aaron Sidford
2013 A* conf
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.
FOCS
Yin Tat Lee, Aaron Sidford
2013 J jnl
Following the Path of Least Resistance : An Õ(m sqrt(n)) Algorithm for the Minimum Cost Flow Problem.
CoRR
Yin Tat Lee, Aaron Sidford
2013 J jnl
Matching the Universal Barrier Without Paying the Costs : Solving Linear Programs with Õ(sqrt(rank)) Linear System Solves.
CoRR
Yin Tat Lee, Aaron Sidford