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.

2022-23 Courses


Stanford Advisees


All Publications


  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Near-optimal Approximate Discrete and Continuous Submodular Function Minimization Axelrod, B., Liu, Y. P., Sidford, A., ACM ASSOC COMPUTING MACHINERY. 2020: 837–53
  • 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
  • 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
  • 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
  • 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
  • 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
  • Stability of the Lanczos Method for Matrix Function Approximation Musco, C., Musco, C., Sidford, A., Assoc Comp Machinery ASSOC COMPUTING MACHINERY. 2018: 1605–24
  • 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
  • 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