Research map / Learning theory and algorithms / Matrix and tensor methods
The Structural Complexity of Matrix-Vector Multiplication
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that Boolean matrix-vector multiplication for matrices with (corrupted) VC-dimension d admits O~(n^2) preprocessing and O~(n^{2-1/d}) query time, extending to Pollard pseudodimension, and uses this to get the first subquadratic high-accuracy dynamic graph algorithms.
Problem
Matrix-vector multiplication is quadratic in the worst and average case and OMv conjecture rules out subquadratic dynamic algorithms, yet practical heuristics are fast on real-world data; the paper seeks a structural explanation for this gap.
Approach
Bound the weight of a minimum spanning tree over Hamming distances between columns (a Delta-labeled tree) by a computational-geometry crossing-number argument, using the corrupted VC-dimension of the matrix; this yields a DFS-based matrix-vector data structure with subquadratic query time for structured matrices.
Key results
- For n x n Boolean matrices with corrupted VC-dimension d, matrix-vector products are computed with O~(n^2) preprocessing and O~(n^{2-1/d}) query time.
- Dynamic Laplacian solver and effective resistance maintained in O~(n^{2-1/d} log 1/epsilon) time per query for graphs with corrupted VC-dimension d, versus naive recomputation in O~(n^2).
- Corollary: Boolean matrix multiplication in O~(n^{3-1/s}) time when matrices and transposes have corrupted VC-dimension bounded by s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Exploit bounded corrupted VC-dimension d | Static Boolean matrix-vector multiplication · Boolean matrix-vector multiplication | query time: \mathrm{nnz}(\mM) -> \widetilde{O}(nm^{1-1/d} + m) | Helped |
| Support row and column insertions/deletions using the dynamic data structure | Boolean matrix-vector multiplication · Dynamic Boolean matrix-vector multiplication | query time: \widetilde O(nm^{1-1/d^*}+m) | Helped |
| Exploit bounded Pollard pseudodimension d and at most T distinct values per column | Non-Boolean matrix-vector multiplication · Non-Boolean matrices | query time: O(T nm^{1-1/d}+m) | Helped |
| Exploit bounded corrupted VC-dimension d | Dynamic Laplacian solver · Dynamic Laplacian systems | query time: \widetilde O(n^{2-1/d}\log 1/\epsilon) | Helped |
| Exploit bounded corrupted VC-dimension d | Dynamic effective-resistance algorithm · Dynamic graphs | query time: \widetilde O(n^{2-1/d}\log 1/\epsilon) | Helped |
| Exploit bounded corrupted VC-dimension d | Dynamic triangle detection · Dynamic graphs | vertex update time: \widetilde{O}(n^{2-1/d}) | Helped |
| Exploit bounded corrupted VC-dimension in both input matrices and their transposes | Boolean matrix multiplication · Boolean matrix multiplication | runtime: \widetilde{O}(n^{3-1/s}) | Helped |
Surprising findings
- The OMv conjecture as commonly stated does not hold for structured matrices with bounded VC-dimension.
Limitations
- Dependence on number of distinct values T in the non-Boolean setting is likely suboptimal (linear rather than logarithmic).
- No matching lower bounds, so optimality of the n^{2-1/d} scaling is unverified.
- Results use corrupted VC-dimension and Pollard pseudodimension parameters which must be bounded in advance; algorithm is theoretical with no empirical evaluation.
Experimental setup
Metrics: preprocessing time query time weight of Delta-labeled spanning tree
Baselines: naive matrix-vector multiplication Boolean matrix-vector algorithms with O(n^2/log^2 n) query time
Builds on: Hamming-distance MST matrix multiplication (Ben-Amram / Alman et al. style algor Welzl crossing-number lemma OMv conjecture Pollard pseudodimension
Closest papers by meaning
- Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products (NeurIPS 2023 · similarity 0.87)
- Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra (ICML 2025 · similarity 0.87)
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.87)
- Approximate Multiplication of Sparse Matrices with Limited Space (AAAI 2021 · similarity 0.87)
- Multiplying Matrices Without Multiplying (ICML 2021 · similarity 0.86)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.