Academic Appointments

Contact

  • Academic
    sidford@stanford.edu
    University - Faculty Department: Management Science and Engineering Position: Assoc Professor
    University - Faculty Department: Computer Science Position: Assoc Professor

Additional Info

Links

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

Stanford Advisees

All Publications

  • Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time van den Brand, J., Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M., Sachdeva, S., Sidford, A., Woodruff, D. P. SIAM. 2024: 2980-2998

    View details for Web of Science ID 001267398700017

  • Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs Bhattacharya, S., Kiss, P., Sidford, A., Wajc, D., Mohar, B., Shinkar, O'Donnell, R. 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 Jambulapati, A., Lee, J. R., Liu, Y. P., Sidford, A., Mohar, B., Shinkar, O'Donnell, R. 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 Carmon, Y., Jambulapati, A., Jin, Y., Sidford, A., Woodruff, D. P. SIAM. 2024: 3685-3723

    View details for Web of Science ID 001267398701007

  • Towards optimal running timesfor optimal transport OPERATIONS RESEARCH LETTERS Blanchet, J., Jambulapati, A., Kent, C., Sidford, A. 2024; 52

    View details for DOI 10.1016/j.orl.2023.11.007

    View details for Web of Science ID 001139143900001

  • Sparsifying Sums of Norms Jambulapati, A., Lee, J. R., Liu, Y. P., Sidford, A., IEEE 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 Jambulapati, A., Musco, C., Li, J., Shiragur, K., Sidford, A., Tian, K., Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023

    View details for Web of Science ID 001229826600022

  • Towards Optimal Effective Resistance Estimation Dwaraknath, R., Karmarkar, I., Sidford, A., Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. 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 Bouland, A., Getachew, Y., Jin, Y., Sidford, A., Tian, K., Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., Scarlett, J. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023

    View details for Web of Science ID 001206894303001

  • Moments, Random Walks, and Limits for Spectrum Approximation Jin, Y., Musco, C., Sidford, A., Singh, A., Neu, G., Rosasco, L. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023

    View details for Web of Science ID 001222719105020

  • Semi-Random Sparse Recovery in Nearly-Linear Time Kelner, J. A., Li, J., Liu, A., Sidford, A., Tian, K., Neu, G., Rosasco, L. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023

    View details for Web of Science ID 001222719102016

  • Improved girth approximation in weighted undirected graphs Kadria, A., Roditty, L., Sidford, A., Williams, V., Zwick, U., Bansal, N., Nagarajan SIAM. 2023: 2242-2255

    View details for Web of Science ID 001288501200173

  • Parallel Submodular Function Minimization Chakrabarty, D., Graur, A., Jiang, H., Sidford, A., Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023

    View details for Web of Science ID 001227224006045

  • Dynamic Maxflow via Dynamic Interior Point Methods van den Brand, J., Liu, Y. P., Sidford, A., Servedio, R. A., Saha, B. 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 Jambulapati, A., Liu, Y. P., Sidford, A., Servedio, R. A., Saha, B. ASSOC COMPUTING MACHINERY. 2023: 196-206

    View details for DOI 10.1145/3564246.3585136

    View details for Web of Science ID 001064640700017

  • A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow van den Brand, J., Chen, L., Peng, R., Kyng, R., Liu, Y. P., Gutenberg, M., Sachdeva, S., Sidford, A., IEEE IEEE COMPUTER SOC. 2023: 503-514

    View details for DOI 10.1109/FOCS57990.2023.00037

    View details for Web of Science ID 001137125900031

  • Sparse Submodular Function Minimization Graur, A., Jiang, H., Sidford, A., IEEE IEEE COMPUTER SOC. 2023: 2071-2080

    View details for DOI 10.1109/FOCS57990.2023.00126

    View details for Web of Science ID 001137125900120

  • Matrix Completion in Almost-Verification Time Kelner, J. A., Li, J., Liu, A., Sidford, A., Tian, K., IEEE 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 Ahmadinejad, A., Peebles, J., Pyne, E., Sidford, A., Vadhan, S., IEEE 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 Carmon, Y., Jambulapati, A., Jin, Y., Lee, Y., Liu, D., Sidford, A., Tian, K., IEEE IEEE COMPUTER SOC. 2023: 2031-2058

    View details for DOI 10.1109/FOCS57990.2023.00124

    View details for Web of Science ID 001137125900118

  • Improved Iteration Complexities for Overconstrained p-Norm Regression Jambulapati, A., Liu, Y. P., Sidford, A., Leonardi, S., Gupta, A. 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 Chakrabarty, D., Graur, A., Jiang, H., Sidford, A., IEEE Comp Soc 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 Carmon, Y., Jambulapati, A., Jin, Y., Sidford, A., Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., Sabato, S. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2022

    View details for Web of Science ID 000899944902032

  • Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers van den Brand, J., Gao, Y., Jambulapati, A., Lee, Y., Liu, Y. P., Peng, R., Sidford, A., Leonardi, S., Gupta, A. 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 Murtagh, J., Reingold, O., Sidford, A., Vadhan, S. 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 Sidford, A., Wang, M., Wu, X., Ye, Y. 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 Carmon, Y., Duchi, J. C., Hinder, O., Sidford, A. 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 van den Brand, J., Lee, Y., Liu, Y. P., Saranurak, T., Sidford, A., Song, Z., Wang, D., Khuller, S., Williams, V. V. ASSOC COMPUTING MACHINERY. 2021: 859-869

    View details for DOI 10.1145/3406325.3451108

    View details for Web of Science ID 000810492500079

  • Towards Tight Bounds on the Sample Complexity of Average-reward MDPs Jin, Y., Sidford, A., Meila, M., Zhang, T. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2021

    View details for Web of Science ID 000683104605008

  • DERANDOMIZATION BEYOND CONNECTIVITY: UNDIRECTED LAPLACIAN SYSTEMS IN NEARLY LOGARITHMIC SPACE SIAM JOURNAL ON COMPUTING Murtagh, J., Reingold, O., Sidford, A., Vadhan, S. 2021; 50 (6): 1892-1922

    View details for DOI 10.1137/20M134109X

    View details for Web of Science ID 000748782500005

  • Lower bounds for finding stationary points I MATHEMATICAL PROGRAMMING Carmon, Y., Duchi, J. C., Hinder, O., Sidford, A. 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 Sidford, A., Wang, M., Yang, L. F., Ye, Y., Chiappa, S., Calandra, R. ADDISON-WESLEY PUBL CO. 2020

    View details for Web of Science ID 000559931303021

  • Efficiently Solving MDPs with Stochastic Mirror Descent Jin, Y., Sidford, A., Daume, H., Singh, A. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2020

    View details for Web of Science ID 000683178505002

  • Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs van den Brand, J., Lee, Y., Nanongkai, D., Peng, R., Saranurak, T., Sidford, A., Song, Z., Wang, D., IEEE 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 Carmon, Y., Jin, Y., Sidford, A., Tian, K., IEEE 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 Ahmadinejad, A., Kelner, J., Murtagh, J., Peebles, J., Sidford, A., Vadhan, S., IEEE IEEE. 2020: 1295-1306

    View details for DOI 10.1109/FOCS46700.2020.00123

    View details for Web of Science ID 000652333400115

  • Unit Capacity Maxflow in Almost O(m(4/3)) Time Kathuria, T., Liu, Y. P., Sidford, A., IEEE IEEE. 2020: 119-130

    View details for DOI 10.1109/FOCS46700.2020.00020

    View details for Web of Science ID 000652333400012

  • Acceleration with a Ball Optimization Oracle Carmon, Y., Jambulapati, A., Jiang, Q., Jin, Y., Lee, Y., Sidford, A., Tian, K., Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., Lin, H. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2020

    View details for Web of Science ID 000627697000016

  • Fast and Space Efficient Spectral Sparsification in Dynamic Streams Kapralov, M., Mousavifar, A., Musco, C., Musco, C., Nouri, N., Sidford, A., Tardos, J., ACM ASSOC COMPUTING MACHINERY. 2020: 1814–33

    View details for Web of Science ID 000554408101055

  • Near-optimal Approximate Discrete and Continuous Submodular Function Minimization Axelrod, B., Liu, Y. P., Sidford, A., ACM ASSOC COMPUTING MACHINERY. 2020: 837–53

    View details for Web of Science ID 000554408100051

  • Solving Tall Dense Linear Programs in Nearly Linear Time van den Brand, J., Lee, Y., Sidford, A., Song, Z., Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. ASSOC COMPUTING MACHINERY. 2020: 775–88

    View details for DOI 10.1145/3357713.3384309

    View details for Web of Science ID 000614624700062

  • Faster Energy Maximization for Faster Maximum Flow Liu, Y. P., Sidford, A., Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. ASSOC COMPUTING MACHINERY. 2020: 803–14

    View details for DOI 10.1145/3357713.3384247

    View details for Web of Science ID 000614624700064

  • Constant Girth Approximation for Directed Graphs in Subquadratic Time Chechik, S., Liu, Y. P., Rotem, O., Sidford, A., Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. ASSOC COMPUTING MACHINERY. 2020: 1010–23

    View details for DOI 10.1145/3357713.3384330

    View details for Web of Science ID 000614624700081

  • A Direct O(1/) Iteration Parallel Algorithm for Optimal Transport Jambulapati, A., Sidford, A., Tian, K., Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000535866903004

  • Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation Charikar, M., Shiragur, K., Sidford, A., Charikar, M., Cohen, E. 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 Sharan, V., Sidford, A., Valiant, G., Charikar, M., Cohen, E. ASSOC COMPUTING MACHINERY. 2019: 890–901

    View details for DOI 10.1145/3313276.3316403

    View details for Web of Science ID 000523199100080

  • Faster Matroid Intersection Chakrabarty, D., Lee, Y., Sidford, A., Singla, S., Wong, S., IEEE 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 Jambulapati, A., Liu, Y. P., Sidford, A., IEEE 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 Jin, Y., Sidford, A., Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000534424303081

  • A General Framework for Symmetric Property Estimation Charikar, M., Shiragur, K., Sidford, A., Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000535866904013

  • Complexity of Highly Parallel Non-Smooth Convex Optimization Bubeck, S., Jiang, Q., Lee, Y., Li, Y., Sidford, A., Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000535866905056

  • Variance Reduction for Matrix Games Carmon, Y., Jin, Y., Sidford, A., Tian, K., Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000535866903006

  • ACCELERATED METHODS FOR NONCONVEX OPTIMIZATION SIAM JOURNAL ON OPTIMIZATION Carmon, Y., Duchi, J. C., Hinder, O., Sidford, A. 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 Pachocki, J., Roditty, L., Sidford, A., Tov, R., Williams, V., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 1374–92

    View details for Web of Science ID 000483921200092

  • Stability of the Lanczos Method for Matrix Function Approximation Musco, C., Musco, C., Sidford, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 1605–24

    View details for Web of Science ID 000483921200106

  • Efficient (O)over-tilde(n/epsilon) Spectral Sketches for the Laplacian and its Pseudoinverse Jambulapati, A., Sidford, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 2487–2503

    View details for Web of Science ID 000483921200160

  • Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes Sidford, A., Wang, M., Wu, X., Ye, Y., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 770–87

    View details for Web of Science ID 000483921200051

  • Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression Gupta, N., Sidford, A., Bengio, S., Wallach, H., Larochelle, H., Grauman, K., CesaBianchi, N., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018

    View details for Web of Science ID 000461823305030

  • Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model Sidford, A., Wang, M., Wu, X., Yang, L. F., Ye, Y., Bengio, S., Wallach, H., Larochelle, H., Grauman, K., CesaBianchi, N., Garnett, R. 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 Sidford, A., Tian, K., Thorup, M. IEEE COMPUTER SOC. 2018: 922–33

    View details for DOI 10.1109/FOCS.2018.00091

    View details for Web of Science ID 000455014500082

  • Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations Cohen, M. B., Kelner, J., Kyng, R., Peebles, J., Peng, R., Rao, A. B., Sidford, A., Thorup, M. IEEE COMPUTER SOC. 2018: 898–909

    View details for DOI 10.1109/FOCS.2018.00089

    View details for Web of Science ID 000455014500080

  • Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification JOURNAL OF MACHINE LEARNING RESEARCH Jain, P., Netrapalli, P., Kakade, S. M., Kidambi, R., Sidford, A. 2018; 18

    View details for Web of Science ID 000438190100001

  • SINGLE PASS SPECTRAL SPARSIFICATION IN DYNAMIC STREAMS SIAM JOURNAL ON COMPUTING Kapralov, M., Lee, Y. T., Musco, C. N., Musco, C. P., Sidford, A. 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 Murtagh, J., Reingold, O., Sidford, A., Vadhan, S., IEEE 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 Chakrabarty, D., Lee, Y., Sidford, A., Wong, S., Hatami, H., McKenzie, P., King ASSOC COMPUTING MACHINERY. 2017: 1220–31

    View details for DOI 10.1145/3055399.3055419

    View details for Web of Science ID 000440317600107

https://orcid.org/0000-0003-2675-7610