# The Structural Complexity of Matrix-Vector Multiplication arXiv: https://arxiv.org/abs/2502.21240 · HTML: https://mlsanity.com/paper/2502.21240/ ## Key facts - Cited by 4 papers in the map (data through 14 Oct 2026). - Builds on 47 of its 106 references that are in the map. - First posted on arXiv 28 Feb 2025. ## Builds on (most cited first, 30 of 47) - [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017) - [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018) - [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020) - [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019) - [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020) - [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015) - [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019) - [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023) - [Solving SDP Faster: A Robust IPM Framework and Efficient Implementation](https://mlsanity.com/paper/2101.08208/) (2021) - [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016) - [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020) - [Solving Tall Dense Linear Programs in Nearly Linear Time](https://mlsanity.com/paper/2002.02304/) (2020) - [Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations](https://mlsanity.com/paper/2210.12320/) (2022) - [Efficient Inverse Maintenance and Faster Algorithms for Linear Programming](https://mlsanity.com/paper/1503.01752/) (2015) - [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017) - [The Communication Complexity of Optimization](https://mlsanity.com/paper/1906.05832/) (2019) - [On Dynamic Graph Algorithms with Predictions](https://mlsanity.com/paper/2307.09961/) (2023) - [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023) - [Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.00661/) (2024) - [Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds](https://mlsanity.com/paper/1905.05067/) (2019) - [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024) - [Online Policy Optimization in Unknown Nonlinear Systems](https://mlsanity.com/paper/2404.13009/) (2024) - [Peer-to-Peer Learning Dynamics of Wide Neural Networks](https://mlsanity.com/paper/2409.15267/) (2024) - [A Faster Interior-Point Method for Sum-of-Squares Optimization](https://mlsanity.com/paper/2202.08489/) (2022) - [Popular conjectures imply strong lower bounds for dynamic problems](https://mlsanity.com/paper/1402.0054/) (2014) - [Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture](https://mlsanity.com/paper/1511.06773/) (2015) - [Practical Computation of Graph VC-Dimension](https://mlsanity.com/paper/2405.07588/) (2024) - [Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication](https://mlsanity.com/paper/1711.04467/) (2017) - [Fully Dynamic Spectral Vertex Sparsifiers and Applications](https://mlsanity.com/paper/1906.10530/) (2019) - [Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary](https://mlsanity.com/paper/2004.08432/) (2020) ## Built on by (most cited first, 4 of 4) - [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025) - [Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling](https://mlsanity.com/paper/2603.03759/) (2026) - [Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.16196/) (2026) - [SMat-Attention: Structured Long-Context Sequence Modeling](https://mlsanity.com/paper/2609.36062/) (2026) ## Abstract (arXiv) We consider the problem of preprocessing an n× n matrix M, and supporting queries that, for any vector v, returns the matrix-vector product M v. This problem has been extensively studied in both theory and practice: on one side, practitioners have developed algorithms that are highly efficient in practice, whereas on the other side, theoreticians have proven that the problem cannot be solved faster than naive multiplication in the worst-case. This lower bound holds even in the average-case, implying that existing average-case analyses cannot explain this gap between theory and practice. Hence, we study the problem for structured matrices. We show that for n× n Boolean matrices of VC-dimension d, the matrix-vector multiplication problem can be solved with widetildeO(n2) preprocessing and widetildeO(n2-1/d) query time. Given the low constant VC-dimensions observed in most real-world data, our results posit an explanation for why the problem can be solved so much faster in practice. Furthermore, we show how to extend this result to the non-Boolean setting with the Pollard pseudodimension. Our results yield the first non-trivial upper bounds for many applications. In previous works, the online matrix-vector (OMv) hypothesis (conjecturing that quadratic time is needed per query, even over the boolean semi-ring) was used to prove many conditional lower bounds, showing that it is impossible to compute and maintain high-accuracy estimates for effective resistance, Laplacian solvers, shortest paths, and triangle detection in graphs subject to node insertions and deletions in subquadratic time. Yet, via a reduction to our matrix-vector multiplication result, we show we can maintain these problems efficiently if the input is structured, providing the first subquadratic upper bounds in the high-accuracy regime.