mlsanityData to 7 Oct 2026

Solving Tall Dense Linear Programs in Nearly Linear Time

arXiv 2002.02304 ↗First posted 6 Feb 2020cs.DS math.OCcited by 21

Not on the map. Why?

Abstract (arXiv)

In this paper we provide an tildeO(nd+d3) time randomized algorithm for solving linear programs with d variables and n constraints with high probability. To obtain this result we provide a robust, primal-dual tildeO(√d)-iteration interior point method inspired by the methods of Lee and Sidford (2014, 2019) and show how to efficiently implement this method using new data-structures based on heavy-hitters, the Johnson-Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain this running time without using fast matrix multiplication and consequently, barring a major advance in linear system solving, our running time is near optimal for solving dense linear programs among algorithms that do not use fast matrix multiplication.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 2; 2023: 5; 2024: 6; 2025: 4.

21 papers.

Sort:

By area:

  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  3. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  4. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  5. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  6. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  7. 2022Semi-Random Sparse Recovery in Nearly-Linear Timecited by 18
  8. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  9. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  10. 2024Testing Calibration in Nearly-Linear Timecited by 9
  11. 2025Dissecting Submission Limit in Desk-Rejections: A Mathematical Analysis of Fairness in AI Conference Policiescited by 9
  12. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
9 more
  1. 2023Projection-Free Online Convex Optimization via Efficient Newton Iterationscited by 4
  2. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  3. 2021Randomized Algorithms for Scientific Computing (RASC)cited by 3
  4. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  5. 2022The Complexity of Dynamic Least-Squares Regressioncited by 2
  6. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  7. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  8. 2025Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Datacited by 1
  9. 2025Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policycited by 0