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
  • 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
  • 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
  • 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
  • Towards optimal running timesfor optimal transport OPERATIONS RESEARCH LETTERS Blanchet, J., Jambulapati, A., Kent, C., Sidford, A. 2024; 52
  • Sparse Submodular Function Minimization Graur, A., Jiang, H., Sidford, A., IEEE IEEE COMPUTER SOC. 2023: 2071-2080
  • 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
  • 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
  • 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
  • Improved girth approximation in weighted undirected graphs Kadria, A., Roditty, L., Sidford, A., Williams, V., Zwick, U., Bansal, N., Nagarajan SIAM. 2023: 2242-2255
  • 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
  • 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
  • Matrix Completion in Almost-Verification Time Kelner, J. A., Li, J., Liu, A., Sidford, A., Tian, K., IEEE IEEE COMPUTER SOC. 2023: 2102-2128
  • 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
  • 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
  • Sparsifying Sums of Norms Jambulapati, A., Lee, J. R., Liu, Y. P., Sidford, A., IEEE IEEE COMPUTER SOC. 2023: 1953-1962
  • 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
  • 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
  • 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
  • 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
  • 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
  • Improved Lower Bounds for Submodular Function Minimization Chakrabarty, D., Graur, A., Jiang, H., Sidford, A., IEEE Comp Soc IEEE COMPUTER SOC. 2022: 245-254
  • 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
  • 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
  • Deterministic Approximation of Random Walks in Small Space THEORY OF COMPUTING Murtagh, J., Reingold, O., Sidford, A., Vadhan, S. 2021; 17
  • 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
  • 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
  • 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

  • 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
  • Lower bounds for finding stationary points I MATHEMATICAL PROGRAMMING Carmon, Y., Duchi, J. C., Hinder, O., Sidford, A. 2020; 184 (1-2): 71–120
  • 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
  • Efficiently Solving MDPs with Stochastic Mirror Descent Jin, Y., Sidford, A., Daume, H., Singh, A. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2020
  • 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
  • Coordinate Methods for Matrix Games Carmon, Y., Jin, Y., Sidford, A., Tian, K., IEEE IEEE. 2020: 283-293
  • 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
  • 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
  • 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
  • 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
  • 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
  • Unit Capacity Maxflow in Almost O(m(4/3)) Time Kathuria, T., Liu, Y. P., Sidford, A., IEEE IEEE. 2020: 119-130
  • Near-optimal Approximate Discrete and Continuous Submodular Function Minimization Axelrod, B., Liu, Y. P., Sidford, A., ACM ASSOC COMPUTING MACHINERY. 2020: 837–53
  • 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
  • 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
  • Faster Matroid Intersection Chakrabarty, D., Lee, Y., Sidford, A., Singla, S., Wong, S., IEEE IEEE COMPUTER SOC. 2019: 1146–68
  • Parallel Reachability in Almost Linear Work and Square Root Depth Jambulapati, A., Liu, Y. P., Sidford, A., IEEE IEEE COMPUTER SOC. 2019: 1664–86
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Stability of the Lanczos Method for Matrix Function Approximation Musco, C., Musco, C., Sidford, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 1605–24
  • 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
  • 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
  • Coordinate Methods for Accelerating l(infinity) Regression and Faster Approximate Maximum Flow Sidford, A., Tian, K., Thorup, M. IEEE COMPUTER SOC. 2018: 922–33
  • 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
  • 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
  • Subquadratic Submodular Function Minimization Chakrabarty, D., Lee, Y., Sidford, A., Wong, S., Hatami, H., McKenzie, P., King ASSOC COMPUTING MACHINERY. 2017: 1220–31