mlsanityData to 7 Oct 2026

A Faster Small Treewidth SDP Solver

arXiv 2211.06033 ↗First posted 11 Nov 2022math.OC cs.DScited by 36

Not on the map. Why?

Abstract (arXiv)

Semidefinite programming is a fundamental tool in optimization and theoretical computer science. It has been extensively used as a black-box for solving many problems, such as embedding, complexity, learning, and discrepancy. One natural setting of semidefinite programming is the small treewidth setting. The best previous SDP solver under small treewidth setting is due to Zhang-Lavaei '18, which takes n1.5 τ6.5 time. In this work, we show how to solve a semidefinite programming with n × n variables, m constraints and τ treewidth in n τ2ω+0.5 time, where ω < 2.373 denotes the exponent of matrix multiplication. We give the first SDP solver that runs in time in linear in number of variables under this setting. In addition, we improve the running time that solves a linear programming with tau treewidth from n τ2 (Dong-Lee-Ye '21) to n τ(ω+1)/2.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Nov 2022.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 26; 2024: 4; 2025: 3.

36 papers.

Sort:

By area:

  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  2. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  3. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  4. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  5. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  6. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  7. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  8. 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
  9. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  10. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  11. 2023InfoPrompt: Information-Theoretic Soft Prompt Tuning for Natural Language Understandingcited by 29
  12. 2023Differentially Private Attention Computationcited by 25
24 more
  1. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  2. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  3. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  4. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  5. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  6. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  7. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  8. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  9. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 11
  10. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  11. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  12. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  13. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  14. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  15. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  16. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  17. 2023Structured and Fast Optimization: The Kronecker SGD Algorithmcited by 5
  18. 2024How to Inverting the Leverage Score Distribution?cited by 5
  19. 2022A Faster k-means++ Algorithmcited by 4
  20. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  21. 2025Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Datacited by 1
  22. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  23. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  24. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0