Introduction
Matrix-vector multiplication ($Mv$) is a foundational operation in modern computing, serving as the inner loop for tasks ranging from neural network training to massive optimization problems. However, a persistent disconnect exists between theoretical bounds and practical performance. Theoretically, multiplying an $n \times n$ matrix by a vector requires $O(n^2)$ time in the worst and average cases, barring impractical "galactic" algorithms. This limitation forms the basis of the Online Matrix-Vector (OMv) conjecture, which posits quadratic time as a fundamental floor. Yet, in practice, engineers routinely deploy heuristics that execute significantly faster on real-world data.
This paper bridges this gap by demonstrating that real-world data is rarely random; it possesses inherent structure. By parameterizing complexity using the Vapnik-Chervonenkis (VC) dimension—a classic measure from machine learning theory—the authors provide a rigorous subquadratic algorithm for structured data, explaining why practical algorithms frequently outperform worst-case theoretical predictions.
Methodology: Exploiting Structure via VC-Dimension
Traditionally used to measure the capacity of a hypothesis class, the VC-dimension is repurposed here to quantify row redundancy within a matrix. If a matrix exhibits a low VC-dimension, its rows (or columns) share a specific geometric similarity.
Differential Compression
To exploit this similarity, the authors introduce a differential compression algorithm:
- Preprocessing: The algorithm constructs a Minimum Spanning Tree (MST) where vertices are matrix rows and edge weights represent the Hamming distance (the number of differing entries) between them.
- Compression: Instead of storing each row explicitly, the system stores the root row and the differences ($\Delta$) between each subsequent row and its parent in the MST.
- Querying: To compute the matrix-vector product, the algorithm traverses this tree. Because the total "weight" (number of non-zero $\Delta$ entries) of the MST is small for matrices with low VC-dimension, the multiplication process is vastly accelerated.
Handling Noise and Non-Boolean Data
Recognizing that real-world data is rarely pristine, the authors introduce the concept of "Corrupted VC-dimension" to accommodate matrices with noisy entries while preserving subquadratic performance. Furthermore, they extend their framework to non-Boolean matrices utilizing the Pollard pseudodimension.
Empirical Validation
The theoretical framework was validated using numerical simulations designed to test the relationship between VC-dimension ($d$) and runtime:
- Synthetic Halfspace Matrices: The authors generated $n \times n$ binary matrices ($n=4096$) derived from linear classifiers in $d$-dimensional space, guaranteeing a precise VC-dimension of $d$.
- Real-World Context: The study aligns with existing literature demonstrating that real-world datasets, such as protein interaction networks or Internet topologies, typically exhibit remarkably low VC-dimensions (often between 3 and 8).
In these simulations, the MST-based algorithm significantly outperformed standard optimized libraries as $d$ remained small, corroborating the theoretical scaling.
Key Results and Implications
The primary theoretical breakthrough is a drastic reduction in query time. For an $n \times n$ Boolean matrix with VC-dimension $d$, the query time drops from $O(n^2)$ to $\tilde{O}(n^{2-1/d})$ after $\tilde{O}(n^2)$ preprocessing. For a VC-dimension of 2, this yields a query time of roughly $O(n^{1.5})$.
Bypassing the OMv Conjecture in Dynamic Graphs
The OMv conjecture has long been a pillar of fine-grained complexity, used to prove conditional lower bounds for numerous dynamic graph problems. By proving that low VC-dimension guarantees the existence of a low-weight spanning tree, this paper demonstrates that these hardness results can be bypassed for structured graphs.
The authors provide the first subquadratic upper bounds in the high-accuracy regime for several dynamic graph problems subject to node insertions and deletions, including:
- Dynamic Laplacian Solvers: Maintaining solutions to $Lx=b$ as the graph evolves.
- Effective Resistance: Estimating the electrical distance between nodes.
- Shortest Paths and Triangle Detection: Efficiently maintaining path lengths and identifying 3-cycles.
Limitations and Future Directions
While groundbreaking, the approach has a few limitations that present avenues for future research:
- Non-Boolean Scaling: For non-Boolean matrices, the runtime currently scales linearly with $T$ (the number of unique values per column). The authors hypothesize this could be optimized to a logarithmic dependence ($\log T$).
- Optimality: It remains an open question whether the $\tilde{O}(n^{2-1/d})$ bound is strictly optimal, leaving room for potentially faster algorithms exploiting low VC-dimension.
- Preprocessing Overhead: The $\tilde{O}(n^2)$ preprocessing time is acceptable for static matrices subject to numerous queries, but reducing this overhead would enhance practicality for highly dynamic datasets.
Summary updated