The Structural Complexity of Matrix-Vector Multiplication

Emile Anand, Jan van den Brand, Rose McCarty

Abstract: We consider the problem of preprocessing an $n \times n$ matrix $M$ to support queries that, for any vector $v$, return the matrix-vector product $Mv$. While the Online Matrix-Vector (OMv) conjecture suggests a quadratic lower bound for this problem in the worst and average cases, practitioners frequently achieve subquadratic performance in real-world applications. This paper resolves this discrepancy by introducing a structural framework based on the Vapnik-Chervonenkis (VC) dimension. We demonstrate that for matrices with a VC-dimension $d$, the matrix-vector product can be computed in $\tilde{O}(n^{2-1/d})$ query time. Our results extend to corrupted matrices and real-valued data, providing the first subquadratic upper bounds for several long-standing problems in dynamic graph algorithms.

Introduction

In the landscape of computational complexity, the matrix-vector multiplication problem—given an $n \times n$ matrix $M$, compute $Mv$ for an arbitrary vector $v$—occupies a central role. Theoretically, this operation is governed by the Online Matrix-Vector (OMv) conjecture, which posits that no algorithm can significantly beat the naive $O(n^2)$ approach, even with extensive preprocessing. This lower bound has been used to prove conditional hardness for a wide array of dynamic graph problems, including shortest paths and Laplacian solvers.

However, a significant "theory-practice gap" exists. In fields like machine learning and network analysis, matrix-vector products are computed with efficiencies that defy the $O(n^2)$ bottleneck. This paper argues that the discrepancy arises because theoretical lower bounds assume worst-case or random inputs, whereas real-world data possesses inherent structure. By quantifying this structure using the VC-dimension, we provide a theoretical foundation for the subquadratic performance observed in practice.

Quantifying Structure via VC-Dimension

The core contribution of this work is the application of the Vapnik-Chervonenkis (VC) dimension to matrix complexity. Originally a tool from statistical learning theory used to measure the capacity of set systems, the VC-dimension $d$ here describes the complexity of the relationships between the rows and columns of a matrix.

We show that structure is a nearly universal feature of non-random data. Specifically, we prove that any "non-trivial" class of matrices that is closed under the removal of rows or columns (a hereditary class) must have a constant VC-dimension. Empirical evidence supports this: real-world graphs, such as protein-protein interaction networks and internet topologies, typically exhibit very low VC-dimensions, often between 3 and 8.

The MST-Based Algorithmic Approach

To exploit this structure, we propose an algorithm centered on the construction of $\Delta$-labeled Spanning Trees. Instead of treating each row of the matrix as an independent vector, the algorithm constructs a Minimum Spanning Tree (MST) where the edges represent the Hamming distance (the number of differing entries) between rows.

If a matrix has a low VC-dimension, its rows are inherently "similar," resulting in a "light" spanning tree. By traversing this tree, the algorithm can compute the product $Mv$ by updating the result incrementally rather than scanning every entry for every row. This reduces the query time to $\tilde{O}(n^{2-1/d})$.

Crucially, this algorithm is structure-agnostic. It does not require prior knowledge of the matrix's VC-dimension or its specific geometric properties; it simply builds the MST, and if structure exists, the speedup occurs automatically.

Robustness and Real-Valued Extensions

Recognizing that real-world data is often noisy, we introduce the concept of corrupted VC-dimension. Our bounds remain valid even if a matrix is obtained by (possibly adversarially) corrupting a subquadratic number of entries in an otherwise low-VC-dimension matrix. This ensures the algorithm's utility in practical, "messy" environments.

Furthermore, we extend our results from Boolean (0/1) matrices to real-valued matrices using the Pollard pseudodimension. This makes the framework applicable to a broader range of problems, including neural network weights and general optimization tasks, where entries are not restricted to binary values.

Breaking Conditional Lower Bounds

This structural approach has profound implications for dynamic graph algorithms. Many problems, such as maintaining high-accuracy estimates for shortest paths, effective resistance, and triangle detection in graphs subject to node updates, were previously thought to require quadratic time per update due to the OMv conjecture.

By reducing these problems to matrix-vector multiplication on structured matrices, we provide the first subquadratic upper bounds in the high-accuracy regime. For example, on a planar graph (which has a VC-dimension of 4), our results allow for significantly faster updates than previously thought possible.

Conclusion and Future Work

This work bridges the gap between the theoretical hardness of matrix operations and their practical efficiency. By shifting the focus from worst-case randomness to structural complexity, we provide a new lens through which to analyze algorithmic performance.

Future research will focus on optimizing the dependence on the number of unique values in real-valued matrices—potentially moving from linear to logarithmic scaling—and exploring whether the $\tilde{O}(n^{2-1/d})$ bound represents the absolute theoretical limit for structured matrix-vector multiplication. Currently, the $O(n^2)$ preprocessing cost remains a hurdle for extremely high-frequency dynamic data, suggesting a fertile ground for further optimization.

Summary updated

Abstract

We consider the problem of preprocessing an $n\times n$ matrix M, and supporting queries that, for any vector v, returns the matrix-vector product Mv. 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 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. Therefore, we study the problem for structured matrices. We show that for $n\times n$ matrices of VC-dimension d, the matrix-vector multiplication problem can be solved with $\tilde{O}(n^2)$ preprocessing and $\tilde O(n^{2-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. Moreover, our bounds hold even if the matrix does not have a low VC-dimension, but is obtained by (possibly adversarially) corrupting at most a subquadratic number of entries of any unknown low VC-dimension matrix. Our results yield the first non-trivial upper bounds for many applications. In previous works, the online matrix-vector hypothesis (conjecturing that quadratic time is needed per query) was used to prove many conditional lower bounds, showing that it is impossible to compute and maintain high-accuracy estimates for shortest paths, Laplacian solvers, effective resistance, 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 the aforementioned problems efficiently if the input is structured, providing the first subquadratic upper bounds in the high-accuracy regime.
BibTeX
@inproceedings{anand2025structural,
  author = {Emile Anand and Jan van den Brand and Rose McCarty},
  title = {{The Structural Complexity of Matrix-Vector Multiplication}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=tGLZj8GWx3},
}
Figure