mlsanityData to 7 Oct 2026

Solving Linear Programs in the Current Matrix Multiplication Time

arXiv 1810.07896 ↗First posted 18 Oct 2018cs.DScited by 100

Not on the map. Why?

Abstract (arXiv)

This paper shows how to solve linear programs of the form minAx=b,x≥0 c^top x with n variables in time O^*((nω+n2.5-α/2+n2+1/6) log(n/δ)) where ω is the exponent of matrix multiplication, α is the dual exponent of matrix multiplication, and δ is the relative accuracy. For the current value of ω~2.37 and α~0.31, our algorithm takes O^*(nω log(n/δ)) time. When ω = 2, our algorithm takes O^*(n2+1/6 log(n/δ)) time. Our algorithm utilizes several new concepts that we believe may be of independent interest: bullet We define a stochastic central path method. bullet We show how to maintain a projection matrix √WAtop(AWAtop)-1A√W in sub-quadratic time under ℓ2 multiplicative changes in the diagonal matrix W.

Key facts. Cited by 100 papers in the map (data through 7 Oct 2026). First posted on arXiv 18 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 12; 2023: 40; 2024: 18; 2025: 12; 2026: 3.

100 papers.

Sort:

By area:

  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  2. 2021Evaluating Gradient Inversion Attacks and Defenses in Federated Learningcited by 196
  3. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  4. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  5. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  6. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  7. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  8. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  9. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  10. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  11. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  12. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
38 more
  1. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 29
  2. 2023Differentially Private Attention Computationcited by 25
  3. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  4. 2022A Sublinear Adversarial Training Algorithmcited by 22
  5. 2021Pareto Domain Adaptationcited by 20
  6. 2022Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptionscited by 20
  7. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  8. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  9. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  10. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  11. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  12. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  13. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  14. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  15. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  16. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  17. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  18. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  19. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  20. 2023Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programmingcited by 10
  21. 2024PMGDA: A Preference-based Multiple Gradient Descent Algorithmcited by 10
  22. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  23. 2023Improved Active Multi-Task Representation Learning via Lassocited by 9
  24. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  25. 2023State-wise Constrained Policy Optimizationcited by 9
  26. 2024Testing Calibration in Nearly-Linear Timecited by 9
  27. 2025Dissecting Submission Limit in Desk-Rejections: A Mathematical Analysis of Fairness in AI Conference Policiescited by 9
  28. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  29. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  30. 2021Slowly Varying Regression under Sparsitycited by 7
  31. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  32. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  33. 2025Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Boundcited by 7
  34. 2021Fairness Maximization among Offline Agents in Online-Matching Marketscited by 6
  35. 2022Towards Optimization and Model Selection for Domain Generalization: A Mixup-guided Solutioncited by 6
  36. 2023Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Gamescited by 6
  37. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  38. 2024Truncated Variance Reduced Value Iterationcited by 6

50 most cited of 100 All 100 (JSON)