Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
The Structural Complexity of Matrix-Vector Multiplication
Authors: Emile Anand, Jan van den Brand, Rose McCarty
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our work proves theoretic guarantees for this speed-up parameterized by the (corrupted) VC-dimension. While the main contribution of this work is to have theoretic guarantees and explanation for why the algorithm is efficient in practice, we here complement the result with a few experiments. |
| Researcher Affiliation | Academia | Emile Anand Georgia Institute of Technology Atlanta, GA 30308 EMAIL Jan van den Brand Georgia Institute of Technology Atlanta, GA 30308 EMAIL Rose Mc Carty Georgia Institute of Technology Atlanta, GA 30308 EMAIL |
| Pseudocode | Yes | Algorithm 1 Online Matrix-vector multiplication (given a -labeled tree of M ) Require: Input matrix M {0, 1}m n, and a -labeled tree of M denoted by T and rooted at r. Require: Input vector v Rn. Initialize: Φ = 0m Φr = M r v Run DFS on T from root r. Whenever DFS visits a vertex x V via some edge (y, x), then set Φx = Φy + x,yv Return Φ |
| Open Source Code | Yes | 3The code for the experiments is available at https://github.com/emiletimothy/structural_ complexity_of_matrix_vector_multiplication |
| Open Datasets | No | Matrix Generation. Since we want to study the complexity dependence on d, we fix the matrix dimension to n = 212 = 4096 and run experiments for d = 2, ..., 12. The maximum d is 12 because the VC-dimension log(n) = 12 so we do not need to consider d > log(n). The matrix size n was picked due to execution time constraints. The n n Binary matrices are generated by sampling i.i.d uniform a(i) [0, 1]d, b(i) [0, d/2] for i = 1, ..., n and x(j) [0, 1]d for j = 1, ..., n, and letting Mi,j = 1{a(i) x(j) b(i)}. The range for the b(i) was chosen so that neither M nor 1 M are sparse, which otherwise would allow for naive matrix multiplication to already beat O(n2) time. The set system of linear classifiers has VC-dimension d, so the corrupted VC-dimension of M is upper bounded by d. This implies that the respective MST has weight at most e O(n2 1/d). Figure 1 shows the observed weight of the MST relative to the ambient dimension d. The MST was computed exactly since easier to implement and the preprocessing time complexity is not focus of this work. |
| Dataset Splits | No | The paper generates synthetic data based on a specified process rather than using pre-existing datasets with defined splits. |
| Hardware Specification | Yes | The experiments were conducted on an Apple M4 Pro mac OS model with 12 physical cores / threads, and 48 GB unified memory RAM, and an Apple Accelerate Framework BLAS backend. |
| Software Dependencies | No | The paper mentions 'naive numpy matrix vector multiplication' and 'Apple Accelerate Framework BLAS backend' but does not provide specific version numbers for these software components. |
| Experiment Setup | Yes | Matrix Generation. Since we want to study the complexity dependence on d, we fix the matrix dimension to n = 212 = 4096 and run experiments for d = 2, ..., 12. The maximum d is 12 because the VC-dimension log(n) = 12 so we do not need to consider d > log(n). The matrix size n was picked due to execution time constraints. The n n Binary matrices are generated by sampling i.i.d uniform a(i) [0, 1]d, b(i) [0, d/2] for i = 1, ..., n and x(j) [0, 1]d for j = 1, ..., n, and letting Mi,j = 1{a(i) x(j) b(i)}. The range for the b(i) was chosen so that neither M nor 1 M are sparse, which otherwise would allow for naive matrix multiplication to already beat O(n2) time. The set system of linear classifiers has VC-dimension d, so the corrupted VC-dimension of M is upper bounded by d. This implies that the respective MST has weight at most e O(n2 1/d). Figure 1 shows the observed weight of the MST relative to the ambient dimension d. The MST was computed exactly since easier to implement and the preprocessing time complexity is not focus of this work. Complexity. For the matrix vector products we generate i.i.d. uniform vectors v [0, 1]n. For each d, we compute 1000 matrix vector products and measure the run time. |