Aaron Sidford

All Publications

• Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers ACM TRANSACTIONS ON ALGORITHMS Jambulapati, A., Sidford, A. 2025; 21 (3)

  View details for DOI 10.1145/3593809

  View details for Web of Science ID 001543243600007

• Extracting Dual Solutions via Primal Optimizers Carmon, Y., Jambulapati, A., O'Carroll, L., Sidford, A. edited by Meka, R. SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2025

  View details for DOI 10.4230/LIPIcs.ITCS.2025.29

  View details for Web of Science ID 001532717300029

• Efficient Convex Optimization Requires Superlinear Memory JOURNAL OF THE ACM Marsden, A., Sharan, V., Sidford, A., Valiant, G. 2024; 71 (6)

  View details for DOI 10.1145/3689208

  View details for Web of Science ID 001391326700006

• 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. edited by Woodruff, D. P. SIAM. 2024: 2980-2998

  View details for Web of Science ID 001267398700017

• UNIT CAPACITY MAXFLOW IN ALMOST m 4 / TIME SIAM JOURNAL ON COMPUTING Kathuria, T., Liu, Y. P., Sidford, A. 2024; 53 (6): OCS20175-OCS20204

  View details for DOI 10.1137/20M1383525

  View details for Web of Science ID 001406377200010

• Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs Bhattacharya, S., Kiss, P., Sidford, A., Wajc, D. edited by 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. edited by 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. edited by 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

• Towards Optimal Effective Resistance Estimation Dwaraknath, R., Karmarkar, I., Sidford, A. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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

• 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

• Structured Semidefinite Programming for Recovering Structured Preconditioners Jambulapati, A., Musco, C., Li, J., Shiragur, K., Sidford, A., Tian, K. edited by 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

• 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

• Improved Iteration Complexities for Overconstrained p-Norm Regression Jambulapati, A., Liu, Y. P., Sidford, A. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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

• 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

• Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation Charikar, M., Shiragur, K., Sidford, A. edited by 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. edited by 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

• 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. edited by 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. edited by 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. edited by 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. edited by 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

• A Direct O(1/) Iteration Parallel Algorithm for Optimal Transport Jambulapati, A., Sidford, A., Tian, K. edited by 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

• 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. edited by 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. edited by 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. edited by 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. edited by 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. edited by 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