Aaron Sidford
Associate Professor of Management Science and Engineering and of Computer Science
Academic Appointments
-
Associate Professor, Management Science and Engineering
-
Associate Professor, Computer Science
Current Research and Scholarly Interests
My research interests lie broadly in the optimization, the theory of computation, and the design and analysis of algorithms. I am particularly interested in work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures.
2024-25 Courses
- Combinatorial Optimization
CME 310, CS 261, MS&E 315 (Win) - Introduction to Optimization (Accelerated)
MS&E 111X, MS&E 211X (Spr) - Optimization Algorithms
CME 334, CS 369O, MS&E 312 (Aut) -
Independent Studies (9)
- Advanced Reading and Research
CS 499 (Aut, Win, Spr, Sum) - Advanced Reading and Research
CS 499P (Aut, Win, Spr, Sum) - Curricular Practical Training
CS 390A (Aut, Win, Spr, Sum) - Curricular Practical Training
CS 390B (Aut, Win, Spr, Sum) - Curricular Practical Training
CS 390C (Aut, Win, Spr, Sum) - Directed Reading and Research
MS&E 408 (Aut, Win, Spr, Sum) - Independent Project
CS 399 (Aut, Win, Spr, Sum) - Ph.D. Research
CME 400 (Aut, Win, Spr, Sum) - Research
PHYSICS 490 (Aut, Win, Spr, Sum)
- Advanced Reading and Research
-
Prior Year Courses
2023-24 Courses
- Introduction to Optimization (Accelerated)
MS&E 111X, MS&E 211X (Spr) - Optimization Algorithms
CME 334, CS 369O, MS&E 312 (Win)
2022-23 Courses
- Introduction to Optimization (Accelerated)
ENGR 62X, MS&E 111X, MS&E 211X (Spr) - Optimization Algorithms
CME 334, CS 369O, MS&E 312 (Aut) - Optimization and Algorithmic Paradigms
CS 261 (Win)
2021-22 Courses
- Discrete Mathematics and Algorithms
CME 305, MS&E 316 (Win)
- Introduction to Optimization (Accelerated)
Stanford Advisees
-
Doctoral Dissertation Reader (AC)
Aaron Mishkin -
Doctoral Dissertation Advisor (AC)
Andrei Graur -
Master's Program Advisor
Young Chen, Tomas Di Felice, Eric Kuang, Pierre-Amaury Laforcade, Schwinn Saereesitthipitak, Laura Wu, Yuxin Wu -
Doctoral Dissertation Co-Advisor (AC)
Ishani Karmarkar, Chenyi Zhang -
Doctoral (Program)
Jennifer Chen, Jiale Chen, Liam O'Carroll, Ta-Wei Tu
All Publications
-
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
SIAM. 2024: 2980-2998
View details for Web of Science ID 001267398700017
-
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
ASSOC COMPUTING MACHINERY. 2024: 59-70
View details for DOI 10.1145/3618260.3649648
View details for Web of Science ID 001254099900008
-
Sparsifying Generalized Linear Models
ASSOC COMPUTING MACHINERY. 2024: 1665-1675
View details for DOI 10.1145/3618260.3649684
View details for Web of Science ID 001254099900153
-
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions
SIAM. 2024: 3685-3723
View details for Web of Science ID 001267398701007
-
Towards optimal running timesfor optimal transport
OPERATIONS RESEARCH LETTERS
2024; 52
View details for DOI 10.1016/j.orl.2023.11.007
View details for Web of Science ID 001139143900001
-
Sparse Submodular Function Minimization
IEEE COMPUTER SOC. 2023: 2071-2080
View details for DOI 10.1109/FOCS57990.2023.00126
View details for Web of Science ID 001137125900120
-
Towards Optimal Effective Resistance Estimation
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023
View details for Web of Science ID 001229826605010
-
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023
View details for Web of Science ID 001206894303001
-
Moments, Random Walks, and Limits for Spectrum Approximation
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023
View details for Web of Science ID 001222719105020
-
Improved girth approximation in weighted undirected graphs
SIAM. 2023: 2242-2255
View details for Web of Science ID 001288501200173
-
Dynamic Maxflow via Dynamic Interior Point Methods
ASSOC COMPUTING MACHINERY. 2023: 1215-1228
View details for DOI 10.1145/3564246.3585135
View details for Web of Science ID 001064640700100
-
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
ASSOC COMPUTING MACHINERY. 2023: 196-206
View details for DOI 10.1145/3564246.3585136
View details for Web of Science ID 001064640700017
-
Matrix Completion in Almost-Verification Time
IEEE COMPUTER SOC. 2023: 2102-2128
View details for DOI 10.1109/FOCS57990.2023.00129
View details for Web of Science ID 001137125900123
-
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs
IEEE COMPUTER SOC. 2023: 846-854
View details for DOI 10.1109/FOCS57990.2023.00054
View details for Web of Science ID 001137125900048
-
ReSQueing Parallel and Private Stochastic Convex Optimization
IEEE COMPUTER SOC. 2023: 2031-2058
View details for DOI 10.1109/FOCS57990.2023.00124
View details for Web of Science ID 001137125900118
-
Sparsifying Sums of Norms
IEEE COMPUTER SOC. 2023: 1953-1962
View details for DOI 10.1109/FOCS57990.2023.00119
View details for Web of Science ID 001137125900113
-
Structured Semidefinite Programming for Recovering Structured Preconditioners
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023
View details for Web of Science ID 001229826600022
-
Semi-Random Sparse Recovery in Nearly-Linear Time
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023
View details for Web of Science ID 001222719102016
-
Parallel Submodular Function Minimization
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023
View details for Web of Science ID 001227224006045
-
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
IEEE COMPUTER SOC. 2023: 503-514
View details for DOI 10.1109/FOCS57990.2023.00037
View details for Web of Science ID 001137125900031
-
Improved Iteration Complexities for Overconstrained p-Norm Regression
ASSOC COMPUTING MACHINERY. 2022: 529-542
View details for DOI 10.1145/3519935.3519971
View details for Web of Science ID 000852709400044
-
Improved Lower Bounds for Submodular Function Minimization
IEEE COMPUTER SOC. 2022: 245-254
View details for DOI 10.1109/FOCS54457.2022.00030
View details for Web of Science ID 000909382900023
-
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2022
View details for Web of Science ID 000899944902032
-
Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
ASSOC COMPUTING MACHINERY. 2022: 543-556
View details for DOI 10.1145/3519935.3520068
View details for Web of Science ID 000852709400045
-
Deterministic Approximation of Random Walks in Small Space
THEORY OF COMPUTING
2021; 17
View details for DOI 10.4086/toc.2021.v017a004
View details for Web of Science ID 000702767600002
-
Variance reduced value iteration and faster algorithms for solving Markov decision processes
NAVAL RESEARCH LOGISTICS
2021
View details for DOI 10.1002/nav.21992
View details for Web of Science ID 000642314100001
-
Lower bounds for finding stationary points II: first-order methods
MATHEMATICAL PROGRAMMING
2021; 185 (1-2): 315–55
View details for DOI 10.1007/s10107-019-01431-x
View details for Web of Science ID 000608923300010
-
Minimum Cost Flows, MDPs, and l(1)-Regression in Nearly Linear Time for Dense Instances
ASSOC COMPUTING MACHINERY. 2021: 859-869
View details for DOI 10.1145/3406325.3451108
View details for Web of Science ID 000810492500079
-
DERANDOMIZATION BEYOND CONNECTIVITY: UNDIRECTED LAPLACIAN SYSTEMS IN NEARLY LOGARITHMIC SPACE
SIAM JOURNAL ON COMPUTING
2021; 50 (6): 1892-1922
View details for DOI 10.1137/20M134109X
View details for Web of Science ID 000748782500005
-
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2021
View details for Web of Science ID 000683104605008
-
Lower bounds for finding stationary points I
MATHEMATICAL PROGRAMMING
2020; 184 (1-2): 71–120
View details for DOI 10.1007/s10107-019-01406-y
View details for Web of Science ID 000578114700003
-
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
ADDISON-WESLEY PUBL CO. 2020
View details for Web of Science ID 000559931303021
-
Efficiently Solving MDPs with Stochastic Mirror Descent
JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2020
View details for Web of Science ID 000683178505002
-
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
IEEE. 2020: 919-930
View details for DOI 10.1109/FOCS46700.2020.00090
View details for Web of Science ID 000652333400082
-
Coordinate Methods for Matrix Games
IEEE. 2020: 283-293
View details for DOI 10.1109/FOCS46700.2020.00035
View details for Web of Science ID 000652333400027
-
High-precision Estimation of Random Walks in Small Space
IEEE. 2020: 1295-1306
View details for DOI 10.1109/FOCS46700.2020.00123
View details for Web of Science ID 000652333400115
-
Acceleration with a Ball Optimization Oracle
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2020
View details for Web of Science ID 000627697000016
-
Fast and Space Efficient Spectral Sparsification in Dynamic Streams
ASSOC COMPUTING MACHINERY. 2020: 1814–33
View details for Web of Science ID 000554408101055
-
Solving Tall Dense Linear Programs in Nearly Linear Time
ASSOC COMPUTING MACHINERY. 2020: 775–88
View details for DOI 10.1145/3357713.3384309
View details for Web of Science ID 000614624700062
-
Constant Girth Approximation for Directed Graphs in Subquadratic Time
ASSOC COMPUTING MACHINERY. 2020: 1010–23
View details for DOI 10.1145/3357713.3384330
View details for Web of Science ID 000614624700081
-
Unit Capacity Maxflow in Almost O(m(4/3)) Time
IEEE. 2020: 119-130
View details for DOI 10.1109/FOCS46700.2020.00020
View details for Web of Science ID 000652333400012
-
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
ASSOC COMPUTING MACHINERY. 2020: 837–53
View details for Web of Science ID 000554408100051
-
Faster Energy Maximization for Faster Maximum Flow
ASSOC COMPUTING MACHINERY. 2020: 803–14
View details for DOI 10.1145/3357713.3384247
View details for Web of Science ID 000614624700064
-
A General Framework for Symmetric Property Estimation
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019
View details for Web of Science ID 000535866904013
-
Faster Matroid Intersection
IEEE COMPUTER SOC. 2019: 1146–68
View details for DOI 10.1109/FOCS.2019.00072
View details for Web of Science ID 000510015300063
-
Parallel Reachability in Almost Linear Work and Square Root Depth
IEEE COMPUTER SOC. 2019: 1664–86
View details for DOI 10.1109/FOCS.2019.00098
View details for Web of Science ID 000510015300092
-
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019
View details for Web of Science ID 000534424303081
-
Complexity of Highly Parallel Non-Smooth Convex Optimization
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019
View details for Web of Science ID 000535866905056
-
Variance Reduction for Matrix Games
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019
View details for Web of Science ID 000535866903006
-
A Direct O(1/) Iteration Parallel Algorithm for Optimal Transport
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019
View details for Web of Science ID 000535866903004
-
Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
ASSOC COMPUTING MACHINERY. 2019: 780–91
View details for DOI 10.1145/3313276.3316398
View details for Web of Science ID 000523199100070
-
Memory-Sample Tradeoffs for Linear Regression with Small Error
ASSOC COMPUTING MACHINERY. 2019: 890–901
View details for DOI 10.1145/3313276.3316403
View details for Web of Science ID 000523199100080
-
ACCELERATED METHODS FOR NONCONVEX OPTIMIZATION
SIAM JOURNAL ON OPTIMIZATION
2018; 28 (2): 1751–72
View details for DOI 10.1137/17M1114296
View details for Web of Science ID 000436991600031
-
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners
ASSOC COMPUTING MACHINERY. 2018: 1374–92
View details for Web of Science ID 000483921200092
-
Efficient (O)over-tilde(n/epsilon) Spectral Sketches for the Laplacian and its Pseudoinverse
ASSOC COMPUTING MACHINERY. 2018: 2487–2503
View details for Web of Science ID 000483921200160
-
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018
View details for Web of Science ID 000461823305030
-
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
IEEE COMPUTER SOC. 2018: 898–909
View details for DOI 10.1109/FOCS.2018.00089
View details for Web of Science ID 000455014500080
-
Stability of the Lanczos Method for Matrix Function Approximation
ASSOC COMPUTING MACHINERY. 2018: 1605–24
View details for Web of Science ID 000483921200106
-
Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
ASSOC COMPUTING MACHINERY. 2018: 770–87
View details for Web of Science ID 000483921200051
-
Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018
View details for Web of Science ID 000461823305022
-
Coordinate Methods for Accelerating l(infinity) Regression and Faster Approximate Maximum Flow
IEEE COMPUTER SOC. 2018: 922–33
View details for DOI 10.1109/FOCS.2018.00091
View details for Web of Science ID 000455014500082
-
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification
JOURNAL OF MACHINE LEARNING RESEARCH
2018; 18
View details for Web of Science ID 000438190100001
-
SINGLE PASS SPECTRAL SPARSIFICATION IN DYNAMIC STREAMS
SIAM JOURNAL ON COMPUTING
2017; 46 (1): 456-477
View details for DOI 10.1137/141002281
View details for Web of Science ID 000396677400017
-
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
IEEE. 2017: 801–12
View details for DOI 10.1109/FOCS.2017.79
View details for Web of Science ID 000417425300070
-
Subquadratic Submodular Function Minimization
ASSOC COMPUTING MACHINERY. 2017: 1220–31
View details for DOI 10.1145/3055399.3055419
View details for Web of Science ID 000440317600107