The Structural Complexity of Matrix-Vector Multiplication
Authors: Emile Timothy Anand
Jan van den Brand
Rose McCarty
Venue: NeurIPS 2025 poster ()
Keywords: data structures
VC-dimension
matrix-vector multiplication
matrix multiplication
dynamic high-accuracy algorithms
Primary area: theory
TL;DR: We show that for nxn Boolean matrices with VC-dimension d, we can do matrix-vector multiplication in O(n^{2-1/d}) time, and provide a number of applications and extensions of this result..

Abstract: We consider the problem of preprocessing an $n\times n$ matrix $\mathbf{M}$, and supporting queries that, for any vector $v$, returns the matrix-vector product $\mathbf{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 \emph{structured} matrices. 
We show that for $n\times n$ Boolean matrices of VC-dimension $d$, the matrix-vector multiplication problem can be solved with $\smash{\tilde{O}(n^2)}$ preprocessing and $\smash{\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. 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.

The Structural Complexity of Matrix- Vector Multiplication
Emile Anand'
Jan van den Brand Georgia Institute of Technology Atlanta, GA 30308
Georgia Institute of Technology Atlanta, GA 30308 emi smile@gatech.eet edu
vabrand@gatech.edu
Rose McCartyl
Georgia Institute of Technology
Atlanta, GA 30308 rmccarty30gatech. edu
Abstract
We consider the problem of preprocessing an n x n matrix M, and supporting queries that, for any vector u, returns the matrix-vector product Mr. 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-can analyses cannot explain this gap between theory and practice. Hence, we study the problem for structured matrices. We show that for X n Boolean matrices of VC-dimension d, the matrix-vector multiplication problem can be solved with (n²) preprocessing and O(n--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 much faster in practice. Furthermore, we show how 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 previ- ous 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 compute and maintain high-accuracy estimates for effective resistance, Laplacian solvers, shortest paths, and triangle detection in graphs subject node insertions and deletions in sub- quadratic time. Yet, via a reduction to our matrix-vector vector-multiplication result, we show we can maintain these problems efficiently the input structured, providing the first subquadratic upper bounds in the high-accuracy regime.
Introduction
Computing sequential matrix-vector products is a fundamental subroutine of many iterative
algorithms in machine learning. In optimization [Renegar] 1996. Vempala al. [2200] Lin et al.
2023a (Cauudhari et al.) 22024, computational geometry Har- Peled 2009 Welzl] 1992 Fisikopoulos
and Penarandal 2016). online algorithms
[Lin et al.] 2024 Anand and Qu] 2024 Murray al.
*Work partially done while Cognition Work done while at Princeton University.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

202T], and dynamic algorithms LLu 2024 Jiang et al. 2023 Anand et al. 2024b Jin and Xu 2022]. sequential matrix-vector products are essential subroutines underlying performant algorithms. The current learning revolution is powered by hardware specifically designed to perform such products, as both neural network evaluation and pack-propagation require repeated natrix-vector products [Sørensen 2012) Rumelhart et al. 1986]. Hence, matrix-vector products are arguably one of the most important and fundamental subroutines, with any complexity improvement having wide-ranging implications, and is thus prevalent research topic in both theory and practice.
The problem can be modeled via the following data structure task: construct a data structure that preprocesses a given n X matrix M. After preprocessing, we want to multiply vectors with M faster than naive matrix-vector multiplication. Depending on the application, this matrix M is fixed or the data structure may need to handle changes to M. For instance, when calculating probabilities of random walk (e-g.. the PageRank algorithm PPge et al. 1999). performing the power-method, and evaluating neural network, the matrix is fixed. Conversely, in convex optimization, such as when solving linear or semi-defiitte program, applying Newton-Raphsori method, and training neural network, the matrix is the inverse of Hessian or is given by the network's 's weights, which changes from one iteration to the next [Arriaaa and Vempala 2006 Anand and Liaw 2025].
Beyond speedups due to improved hardware, practitioners have made tremendous progress in accelerating the computation of matrix-vector products through heuristics that run in nnz (M) (the number of non-zero entries of M) worst- time. but which are much faster in practice. This has led speedups in training GNNs [Alves et al., 2024] and other algorithms (Floros al., 2024
Conversely, from a theory perspective there are substantial lower bounds. Gronlund and Larsen (2015) showed that any poly(n) (sp-se data structure for matrix- multiplication over sufficienlly large fields (for instance, R) require 22n² / log n) time. This quadratic lower bound was also proven for arithmetic circuits (Frandsen et al., 2001). While these are worst-case lower bounds, they also hold for the average case [Henzinger et al. 2022]. The only non-trivial upper bounds beating quadratic time are over the Boolean semi-ring (i.e., {0, with x + y minn1, x + y)). In line of works that reduced the problem to finding neighborhoods in a graph and smaller algebraic
products, this query complexity was improved to O(n²) / logg n) [Liberty and Zucker [0066] Williams
2007) and ((n2-o(1) (Larsen and Williams, 2017 Chakraborty et al. However, none of these algorithms are truly subquadratic. i.e., O(n-- for some constant e O.
2018 Abboud et al. 2024
Moreover, while the M(r²) lower bounds only hold over finite fields, even over the Boolean semi-ring it is conjectured that truly subquadratic time algorithm exists [Henzinger et al. 2013). and this is commonly referred to as the OMv (online matrix-vector multiplication) conjecture. In fact, this has led to recent line of works that use the conditional hardness of OMv to prove tight time lower bounds for many dynamic algorithms, such as dynamic matrix inversion [Brand et al., 2019a b). dynamic subgraph connectivity (Henzinger and Neumann, 2016), dynamic regression Jiang et al.] 2023). dynamic range, Langerman's 's problem Uin and Xu 2022]. and the generalized Klee's high-dimensional measure problem (Yildiz and Suri 2012].
In summary, there is a notable difference between the perspectives of this problem in theory and practice: there are heuristics that are fast in practice, but from theoretical perspective the problem is hard, and an entire subarea of fine-gratn grained-complent assumption [Hu and Polak, 2024]. Further, average-cass analyses cannot explain this gap, as even the average-case is provably hard. In this work, we resolve this conflict: since the average-case (i.c., random non-structured inputs) is hard, the observed efficiency of practical algorithms must stem from some inherent structure in real-world data. Thus, we study the complexity for structured inputs.
has been built on this hardness
A popular measure for structural complexity is the Vapnik- -hhnin-Chervonenkis (VC) dimension, which finds many applications in machine learning (Shalev-Shwartz and Ben-David] 2014 Bartlett et al.. 2019), structural graph theory [Nguyen et al. 2024||loo et al. 2016 | Karczmarz and Zheng [024]]
and computational geometry [Har-Peled] 2209 [. Chazelle 1989 Fisikopoulos and Penaranda 2016
(see the preliminaries in Section for definition of the VC-dimension). For Boolean matrices, the VC-dimension has the following. more intuitive, description: it is the size of the largest subset S C [n] of columns such that the rows of the sub-matrix whose columns are restricted to those in S contain every possible string in {0, 1) IS| Many structured objects studied by theoreticians have inherently low VC dimension. For instance, star and interval graphs, and rank-one projection matrices, have VC-dimension 2, planar graphs have VC dimension 4, and any H H-minor free graph has VC dimension at most V [H)) 1. Beyond being an established complexity measure in theory, it has also been

---

empirically observed that real-works data has low VC dimension [Coudert et al. 2024]. We explain this observation via the following structural characterization of matrices with low VC dimension:
Theorem 1.1 (Proof in Appendix D). Consider a hereditary class 0f 0/1-matrices M. meaning that M is closed under row/column deletion (i.e., each matrix M E M is still in M after deleting a row or columm). If M is non-trivial, (i.e., does nol contain every possible matrix), then there exists an absolute constant E N such that the VC-dimension of any matrix in M is at most c.
Presumably, any unknown structure common to real-world matrices should not be lost when deleting rows/columns. Theorem 1.1 does not exclude other matrices (which do not satisfy this hereditary property) from having constant VC-dimension, e.g., adjacency matrices of minor-free graphs.
1.1 Our Results
While theoretical objects such as grid- trid-graphs, intersection graphs, and kernel-matrices have a low VC-dimension, they are not perfect representations of real-world data. For instance, while city street networks are predominantly diagonal streets. Exceptions can also occur due to errors in measurements or other corruptions. To capture such almost low VC-dimension objects, we define the "corrupted VC-dimension."
there always exists exceptions in the form of bridges or few
Definition 1.2 (Corrupted VC-dimension d). The "corrupted VC-dimension" of set system F with m sets is the smallest such that there is another set system F' of VC-dimension S d and F can be obtained from F by adding and/or removing each element toffrom most (m (mm sets.
For matrices M E {0, 10,1,, corrupted VC-dimension d implics the existence of a matrix 1)mXn with at most
L E 1) of VC-dimension S d and a 'corruption' matrix S E 0(m²-1/d) non-zero entries per column, such that M = L + S. Note that the mere existence of such an F (i.e., L) of VC-dimension < dl suffices for F (i.e., M) to have corrupted VC-dimension d. We do not need to know F' or which sets have been corrupted. Also, the VC-dimension of F upper bounds the corrppted VC-dimension of F. Hence, while we state our results for matrices with corrupted VC-dimension d, the proven upper bounds also hold for matrices with VC-dimension d.
We now state the theoretical guarantees of our accelerated matrix-vector vector multiplication algorithm in Theorem 1.3] where the runtimes are parameterized by the corrupted VC dimension measure.
Theorem 1.3. (Static Online Matrix- Vector Multiplication). If matrix M E {0, 1)mxx has corrupted VC-dimension d, then after an ((mm))-imm preprocessing, there a data structure 'D that can compute Me for any v E 1n' in Ö(mm 1id + m) time, with high probability.
The problem of approximating the VC-dimension of any set system within a (2 (2-c) c) accuracy for any e 0 is known to be Dg -hard [Mossel and Umans| 2002]; however, for our theorem, the algorithm does not need to know or compute or even approximate the VC-dimension to achieve this runtime.
Our data structure is based on Björklund and Lingas [000] which proposed an algorithm for Boolean matrix multiplication. Their algorithm computes the matrix-matris product via n matrix- prod- ucts, thus implicitly providing matrix-vector multiplication data structure well. Their complexity depends on the weight of the minimum spanning tree (MST) defined with respect to the Hamming- distance between the rows of M. However, the weight of the MST is On²?) in the worst-case.
This algorithm was recently independently rediscovered in the graph neural networks community Alless et al. 2024] which experimentally verified its efficiency on real-world inputs. Our Theorem 1.3 now gives a theoretical explanation as to why these practical algorithms are much more efficient in practice than the worst-case and average-case lower bounds of 9(mm).
We obtain Theorem via techniques from computational geometry. A line of works [ellzl 1988 B. Chazelle| 1989 Matoušck| [991 Har-Peled 2009) consider the following geometric intersection data structure problem: given set of points in _ preprocess them. Then, given a convex polytope for each query, return whether any of the points intersect the polytope. However, prior work had exponential preprocessing time [Welzl] 1992) or unspecified polynomial time [Matoušek] [99T]. Matrix vector products can be interpreted as 0(m) intersection problems if we only care about Boolean outputs, because in the Boolean case (Mv), + and only if there is an intersection between the position of the non-zero elements in v and the non-zero elements in the i-th row of M. We extend these computational geometry techniques to non-Boolean outputs, and to our more general notion of corrupted VC-dimension. We provide details of this proof in Section 3.2
3

---

In addition to our novel complexity bound, we also provide alternative algorithms to those presented
in Bjöōklludd and Lingas 200T]. Alves et [2024]
We provide more details below.
Dynamic Setting. We extend Theorrm 1.3 by allowing M to undergo row and column updates. The proof is given in Appendix [3.]
Theorem 1.4. (Dynamic Online Matrix- Vector Multiplication). Given a matrix M E {0, } there is a data structure D with (mm) preprocessing time that supports row and column updates (insertions/deletionn)) to M in (n) and (()) time, respectively. Upon querying 'D with vector IR", it oulputs Me in O Onm---1jd + m) time, with high probability, where d' is the largest corrupted VC-dimension of M throughout the history of its updates.
Transposed Matrices. If the VC-dimension of MT is d, then the VC-dimension of M is at most 2d+1 AAssuadd 1983), so Theorem 1.3 runs in (mm! 1-122" + +m) time. To address this slow-down, we extend the a algorithm to bound its complexity by the VC-dimension of M
If M E {0, 1 mm and M E {0, 1 have corrupted VC-dimension d and d' (respectively). then after an ( preprocessing, we show we can compute Me in time (miinmmm-
m, mmn11/1d + n)) with high probability. We do not need to know d or d', as the algorithm automatically achieves the minimum.
Non-Boolean Matrices. The Pollard pseudodimension extends the VC-dimension to non-binary thresholds. It finds many applications in theoretical machine learning (Shalev-Shward and Ben- David 2014 Bartlett al., 2019) and structural graph theory (Karezmarz and Zheng 2024] (see Appendix B 4.4] for a definition of the Pollard pseudodimension). For M E Rmxx" if d bounds the Pollard pseudodimension of M and T bounds the number of unique values per column of M, then by My can be computed in time O(Trm² + m). For T < Ó(1), this is subquadratic.
Theorem B.9
1.2 Applications
Random Walks and PageRank by Scaling, Let A E R be the adjacency matrix of an n-node
graph and let D E Raxn be its degree matrix. The normalized Laplacian is L I-
D D-122 11121/2DD AD
Even though is not Boolean, we can still use Theorem 1.3 since L D (2 Aw) for
w = D 1122g and the product Aw can be computed via Theorem 1.3 The same technique extends to mallom-walk probability matrices, In turn, this allows fast simulations of Markov chains to compute
stationary distributions and iterative computation of the PageRank (Page et al. 1999 via Theorem 1.3
Complexity- Theoretic Implications. The Boolean matrix multiplication (BMM) conjecture states that no algorithm can multiply two boolean X matrices in O time for constant > 0 |Basch et al. [995] Williams and Williams, 2010). This conjecture is used to prove lower bounds on combi- natorial algorithms (i.e., algorithms that do not make use of Strassen-style fast matrix multiplication methods), motivated by the property that fast matrix multiplication, while being theoretically fast (currently 2-33322) Williams et al. [2024)), is very slow in practice due to large constants hidden in O-notation. Hence BMM gives a lower bound on more practical algorithms and can be used to prove that any further complexity improvement would require fast matrix multiplication.
Theorem 1.3 implies that for matrices with corrupted VC-dimension d, BMM can be solved in
( time, allowing for improved combinatorial upper bounds. The BMM problem was the original motivation for Björklund and Lingas [2001], Gasieniec and Lingas 20033. Moreover, as demonstrated in Alves et al. [2024], this algorithm is also highly efficient in practice and does not encounter the large constant of fast matrix multiplication. Therefore, Theorem 1.3 implies that problems with lower bounds based on BMM can be solved more efficiently on structured inputs.
Corollary 1.5. Suppose we are given matrices MI, M2 10,1) where M. has corrupted VC- dimension d, and M. has corrupted VC dimension d' i E (1, Let min(d1, de, d2)2). Then, there is an algorithm for Boolean matrix multiplication which runs in (n2-1/0) time.
Another relevant conjecture is the OMy conjecture, which states that algorithm can preprocess Boolean matrix M {0, 1) paxn in polynomial time, and then answer n queries that compute () for online sequence of Boolean vectors (1)) ..., ((n) E {0, 13 in total time Or23-t). Observe

---

that here the vector (+++1) 1) is only given after the data structure returned Mu hence the use of fast matrix multiplication to compute the matrix product M [u( [..][<0)] is ruled out.
This conjecture is used to prove conditional lower bounds for many dynamic graph problems, such as maintaining shortest paths, effective resistances, reachability, bipartite matching, triangle detection, and many others in graphs undergoing vertex insertions and deletions [Henzinger et al., 2015]. Even using fast matrix multiplication, no algorithm can beat O(n²) time on dense graphs, which is typically equivalent to re-solving them from scratch whenever the graph changes. Since Theorem 1 shows
the OMv conjecture does not hold for structured matrices, it leads to improved dynamic algorithms.
Implications to Dynamic Algorithms. We list some novel dynamic algorithms obtained via this technique, whose upper bounds are only achievable due to their structured nature, otherwise violating either the BMM OMv conjecture. We defer the formal proofs for these results to Appendix [
An important class of linear equations arising practice have form Lx = 6, where of an undirected graph G = (V, E) given by L == D A where D is diagonal matrix such that D.,, dig(i) for E [n] where [ = n, and A is the adjacency matrix of G. There are Laplacian solvers that run in time nearly linear in |E' [Spielman and Teng 2004). We study the problem of constructing dynamic Laplacian solver for L = b, where the Laplacian changes over time through vertex updates to the graph, and each b, is an arbitrary new vector.
the Laplacian
Previous upper bounds could only handle a poly(1 /1e) accuracy by maintaining spectral sparsifiers Abraham et al. 2016) or vertex sparsifiers [Durfee et al. 2019). Moreover, exact or Oloo 1/m)-time dependencies are ruled out by the OMv conjecture since no algorithm beats naive recomputation from scratch in Ö( = Ō(n²) time via nearly-linear time Laplacian solvers (Spielman and Teng 2004]. We give the first result faster than naive recomputation in the high-accuracy log(1/e) regime.
Theorem 1.6. (Dynamic Laplacian Solver). There is a dynamic algorithm that, given dynamic graph G = =V, with corrupted VC-dimension bounded by d, maintains a Laplacian system solver. The data structure supports queries that receive a vector b E IRIV and error parameter > 0. Then, in Ōn 1/d log 1/e) time, the algorithm returns the (approximate) solution x to Lx" = b where - ||00 - -=x'= x=1|1 I <l1z"||1. Each vertex update to G takes (n) time.
With the fast dynamic Laplacian solver, we maintain dynamic effective resistances, which is a critical subroutine in graph clustering (Alev et al.] 2017). fault-tolerant computing (Ghoh et al. 2008
network analysis (Tizghadam and Leon Garcia 2008 Anand and Umans 2023 Anand et al. 2024a
and biological systems [Klein et al. 2022]. as it measures the connectivity between two vertices.
The effective resistance ra 6) between vertices and b in graph G is graph-analog of leverage scores that represents the energy needed to route one unit of electric flow from a b. Formally, let
e, denote the i-th standard basis vector. Then, for all a, b E V. ra b) (e, .s)) LL -y), where L is the Laplacian of G and L' is the Moore-Penrood pseudoinverse of L.
Theorem 1.7. (Dynamic Effective Resistance). There is dynamic algorithu that, given a dynamic graph G (V, with corrupted VC-dimension bounded by d, maintains effective resistances in G. The data structure supports queries that receive a pair of vertices u, v E V and error parameter e <> O. Then, in 2-n2-/dd log 1/e) time, the algorithm returns a (1 <) e)ppproxiimation of the effective resistance. Moreover, each node update to G in the dynamic data structure takes O(n) time.
Our dynamic matrix-vector multiplication data structure also leads to faster dynamic triangle detection algorithms for graphs with corrupted VC-dimension d, which are critical components of fraud detection systems and conmunity-detectionn algorithms. No subquadratic time algorithm exists for vertex updates, conditional on BMM (Abboud and Vassilevska Williams| 2014) or OMv (Henzinger et al. 2013). We show that these lower bounds can be broken on structured graphs.
Theorem 1.8. (Dynamic Triangle Detection). There is algorithm that, given a dynamic graph G= (V, E) with corrupted VC-dimension d, maintains whether G has a triangle or not. Each vertex update takes O(n2-1/d) time and returns Boolean indicator for G containing triangle.
Our techniques lead to faster dynamic approximate algorithms for single-soure distances, where we are tasked with finding the distances from a designated source vertex to every other vertex.
Theorem 1.9. (Dynamic Approximate Single- SSurce Shortest Paths). There is a dynamic algo- rithm that maintains (1 + e) a)appooximatee single- source distances on dynamic unweighted graph
5

---

G (V.)) If the corrupted VC-dimension of G is bounded by d. each node update to G takes O(kn (//n-// time, and querying the distances for any source node takes ( /c) time.
Given metric space M with points and a positive integer k S. n, the k-center problem asks one to select k points, referred to as centers, such that the maximum distance of any point in the metric space to its closest center minimized. It is known that the k-center is NP- to (2 -)-aprroxe for any > 0 Hss and Nemhauser 1979]. The best existing dynamic algorithms (Cruciani et al. 2024 only work with edge updates and use fast matrix multiplication
black-box. We present an algorithm without fast matrix multiplication that supports more powerful vertex updates.
Theorem 1.10. (Dynamic Approximate k-center). Given an unweighted undirected graph G = (V. E), there is dynamic algorithm for (2 + e)-approximate k-center with node update time O(kn ((kn211/2/// /e), where d a bound on the corrupted VC-dimension of G.
1.3 Further Related Work
Boolean matrix multiplication. A line of work shows that the complexity of matrix-vector multi- plication over the Boolean semiring can be mildly subpolynomial. For instance, Williams 2007]
showed that BMM can be computed in On log n) time. In turn, Larsen and Williams 201 7 and
Abboud et al. [2024] extended this to (n //20( ( (log)))
Structured matrices. When the underlying matrix Vandermonde, Toeplitz, Hankel, or Cauchy, body of work shows that they admit fast matrix-vector multiplications through convolutional transformations [Motzkin| [951] Olshevsky and Shokrollahi [200 Pan and Tsigaridas [014]. Orthogonal-vecter (OV) matrices are structured matrices where each row and column receives a label E {0, 1)dh and M.;; = if and only if the corresponding two labels are orthogonal. Similar to our corrupted VC-dimension results, Alman and Vassilevska Williams [2020] show that OV matrices allow fast matrix-vector products if there are few corruptions to the matrix. Matrix products also be accelerated using geometric data structures Lingas (2002). Floderus et al. (0188. Another approach to handle structured inputs is through the algorithms with predictions regime, where some learning algorithm extracts the structure and can predict information about future vectors, leading to faster matrix-vector multiplication algorithms Henzinger et al. 2024]. Brand et al.) (2024).
Dynamic structured graphs. Our dynamic algorithms hold for any structured graph, even if we do not know their structure. When the structure is known, there are specialized dynamic algorithms tailored to the specific graph. These include, for instance, interval graphs Crespelle [2019). Chen cet al. 2024), geometric graphs defined from Kernels (Alman et al., 2020). dynamic planar graphs Korhonen et al. 2024 Abboud and Dahlgaard 2016), and minor free graphs (Dorn al. 2012).
Matrix vector multiplication in optimization. convex optimization, there is a long history on developing data structures to accelerate matrix-vector products. Here the matrices are generally projection matrices that require computation of some matrix inverse. While historically, most research
was on accelerating the maintenance of the matrix inverse [Karmarkar] 1984 Vaidya 1989 Lee and
Sidford 2015] Cohen et al. [02T Lee et al.) 2019 Brand [020]] Jiang et al.) 2021 2020a Huang al.J [2022] Jiang et al., 2022 2020b), this research has progressed so far that the current bottleneck for faster linear program solvers are simple matrix-vector products [Brand et al. 2020 2021
Preliminaries
Notation. Let [n] = {1....,,) n). We use O(-) to hide constant factors, and ((-) to hide polylogarith- ||1 denote the E (Manhattan distance). For a matrix M, let M, and M., denote
mic factors. Let -| its i'th column/row (respectively). For set V we write M RR V for the m X [V] matrix where we can index columns by x E V. i.e. M2, E R For any vector & E R", the Hamming weight of x the number of non-zero entries of also denoted by nnz(z). ). For Boolean vectors I, y E {0, 13"". the Hamming distance between and y is given by ||æ - y/l1. Finally, for any vector x E R" and positive definite matrix L E gaxa define the L-induced norm of x by ||x|| = vx Lx.
VC-Dimension. A range space (or a set system) is pair 3 = (X, R) where X is a set and aet of subsets of X. Let n (A) = {Anr: E R). The VC-dimension of 9 VC(9R) max[[S]: : C X and [SS 2/. The dual range space of R is then given by RT = (R, ([r|æ r)) E X)). and the dual VC-dimension of A is the VC-dimension of R
Any matrix M E {0, 1) pmxx

---

corresponds to set family FM - {f) M. = :iE [m]], i... each row of M is the indicator vector of some set. Through it, we can encode M by the range space Ras = FM). Then, the VC-dimension of M is defined as the VC-dimension of RM. and the dual VC-dimension is the VC-dimension of M Here, a subset S of the columns of M is said to be shattered if each of the 21 many 0/1 strings appears in some row in the restriction of M to the columns in S. Then, the VC-dimension of M is the maximum size of a shattered subset of the columns of M. Therefore, we see that the VC-dimension dm,, of a matrix M E {0, 1 mx satisfies 1 S dm,n log m.
3 The Structural Complexity of Matrix-Vector Multiplication
We present a technical overview of the algorithms and main theorems. We begin this section with an overview of [Börklund and Lingas| (200T), [lves et al. (2024) who established connection between matrix vector products and minimum spanning trees on n points {0, 1)mh, where the edge weights are given by the Hamming distance between two points (i.e., matrix M defines collection of points).
We prove via techniques from computational geometry that the weight of the minimum spanning tree is bounded if the matrix M has corrupted VC-dimension at most d. This yields our main result in Theorem 1.3
Having established this connection, we prove one of our main results in Section 3.2
3.1 Matrix Vector Products via Minimum Spanning Trees
We here recap the algorithm idea by Björklund and Lingas 2001], which was later independently rediscovered by Alves et al. 2024). We also explain how to extend the results from M to M
Differential Compression. Given binary matrix M E {0, 1) mmx, let M, denote its i'th column. We compress M by writing each column M, as the sum of another column M, and a change vector Aryy such that M, = M, + Az.y and Ar.y = M, My. If M, and M, are similar, then is likely to be smaller than the number of nonzero elements of M,. So, it is more efficient to indirectly represent M, with respect to My, instead of through M. This requires an algorithm that finds chain of A's to represent all columns of M: for each column Mg. identify similar column My such that the Hamming weight | il required to represent M, is minimized subject to My. Since the algorithm measures the Hamming distance for each pair of columns in M, we model this compression by an undirected weighted graph G on n vertices, where vertex i represents M,, and the weight of each edge (x. y) is A l1. We can then find Minimum Spanning Tree (MST) of G, which by definition spans G with the minimum sum of edge weights possible. Therefore, any MST of G rooted vertex r defines chain of A 's that, starting r, can represent all the columns of M.
|A
We formalize this intuition by defining the A-labeled spanning tree of a matrix and its weight.
Definition 3.1 (A Lableee spanning tree of matrix M). A A-labeled tree is tree T = (V, with some explicit root x, where each edge e E E is directed away from I and labeled by a vector Ae E RT. We say is a A-labeled spanning tree for matrix M E mgxx if M2 = 0 for root x, and for all edges (i.j) E E we have A.. := M, M,
Definition 3.2 (Weight of a A-labeled spanning tree). For any A-labeled spanning tree of M denoted by T with directed edge-set E, define weight(T) =eer nnv( (A)).
The minimum spanning tree of M is then the A-labeled spanning tree with the smallest possible weight. Given any spanning tree of M, use the weight of the llabeled spanning tree to parameterize the runtime of the vecrix multiplication algorithm. Here, the lower the weight of the labablled spanning tree, the faster the runtime.
Lemma 3.3 (Björklund and Lingas (2001) Alves et al. (2024).
) Given a A-labeled spanning tree T of MT (0, 1) nm and vector 1 we can compute Mr in O(weight(T)) + m) time.
We describe this procedure in Algorithm I
As a quick recap, the algorithm computes My by starting at root node E T of the spanning tree and performing depth-first search (DFS). The algorithm initializes an output vector and computes (Mu), in O(n) time. For each edge (z, y) traversed + by DFS on the tree, the algorithm computes (Mu), = (Mr), + A..2.. The complexity of this iterative procedure is proportional to wTight(T) Eeeprry 8e where for each edge (x. y) in
the A l-beled spanning tree, & the number of non-zeros in A., i.e., the Hamming distance between row x and row y of M. For completeness, we prove Lemma 3.3 in Appendix B.I
7

---

Since the weight of the A-labeled spanning tree of M can be different from the weight of the A- labeled spanning tree of M, we provide new algorithm with an analogous guarantee Lemma 3.4
Lemma 3.4. Given a A-labeled spanning tree T of M E {0, 1 and a vector E R,, there is an algorithm that can compute My in ((weight(T) + n + m) time.
To utilize the A-labeled spanning tree of M, note that Mu- = Σi=1, M. In the special case where M has only two columns, Mu M + M2 = M + 02) + 1,2222 For more columns, this can be extended to require only a product with M, and products with each A. in T. Thus the
complexity is bounded by (m + n + weight(T)). We prove Lemma 3.4 in Appendix B.1
To minimize the time complexity, we compute a MST. In Alves et al. [2024] this was done naively. whereas in Björklund and Lingas (2001) this is done via Theorem 4.2 of Indyk and Motwani [9988.
Lemma 3.5 (Theorem 4.2 of Indyk and Motwani (1998). For e > O, we can compute (1 + e)- approximate MST with respect to the Hamming distance of n points in {0, 1m in time O(mn - I+c)
Theorem 3.6. Given a Boolean in X n. matrix M, we can construct in ((nm) time a A-labeled spanning free whose weight is at most a Olog nf)factor larger than the MST of M.
Proof. Run Lemma 3.5 on the columns of M for = log n to construct an Ollog n) approxxmmae MST in (mm) time. Next, iterate over the edges of the MST and label each tree edge (1; v) by M, MM This takes (mm) time as there are only 1 tree edges and An.y E R O
A R.
3.2 Existence of Low Weight A-labeled Minimum Spanning Trees
The Hamming distance between any two columns in M is at most m. Since there are (n) edges in the A-labeled MST, this gives a coarse bound of (mm) which is achieved for Hadamard matrices. One of our main technical contributions is to prove that A-labeled MST's with low weight exist for structure matrices. We bound the MST's weight parameterized by the corrupted VC-dimension of M.
Theorem 3.7. If a matrix M {0, 1 has corrupted VC-dimension d, then the weight the minimum spanning tree of M is at most 0(m 1-1d log" n).
We show that for matrices M whose transpose M has bounded corrupted VC-dimension, the MST has small weight. For this, we work directly with the definition of VC-dimension and use set terminology, which allows us to use relevant work from Welzl [1988]. This previous work studied bounded VC-dimensions in the context of computational geometry. We here use their results to bound the complexity of matrix vector products.
Definition 3.8 (Set crossings). Let A and r be sets. T crosses A if and only if neither A S r nor Aor = 0 holds. That is, there are x. y E A with E r and &
Definition 3.9 (Spanning Tree). Let A C X be a finite set of elements of a range space (X,R). spanning tree on A is an undirected (unrooted) tree with node set A.
Definition 3.10 (Weight of spanning tree T). A crossing of a range that is crossed by r (i.e,, an edge that has one endpoint in r and the other endpoint in X (r). The crossing number Kep (T) of range E R is the number of crossings of r in T. The weight of tree T is defined as wTT) = EVER Ky, (T).
R in T is an edge in T
This spanning tree corresponds to the A-labeled spanning tree for matrix M. where the range space (X, R) induced by M E 1 mm has ground set X [ni] (i.e., column indices) with the rows of M being the indicator vectors of subsets of X. Thus, a spanning tree Tx for (X, R)) and spanning tree T'M for M both consist of edges connecting elements in [n]] and the number of crossings for an edge (z, y) E Tx equals the number of indices i where (M.), and (Mş); differ. Hence, w(Tx) is the weight of the corresponding A-labeled spanning tree M.
We show that when the dual of (X, R) has corrupted VC-dimension d, then (X, R) has spanning trees with small weight. The literature on finding spanning trees on X with few crossings stems from works in computational geometry from the 1900s [Welzl] 1988 B. Chazelle, 1989 Matoušek [99] Har Peled 2009) which used the trees to preprocess a set of points in Ra and answer queries where for any convex polytope, the query returns a point in the polytope. We transfer their techniques to our problem. The following lemma allows us to prove the existence of a A-labeled spanning tree for matrices whose transpose has bounded VC-dimension. We later extend this to corrupted VC-dimension.
8

---

Lemma 3.11 (Lemma 4.1 of Welzi 1988) ) Let (X, R) be a range space with dual VC-dimension at most d. For every A C X, A n Z I and every multiset Q of ranges in R with [Q] = m, there exists I + y E such that the number of ranges in Q crossing (Ir y) at most Omn- - 1/d log" n). Remark 3.12. The original proof of Lemma 4.1 of Welza [198]] gives a bound of O(mn 10 1/d log n) but hides some terms that depend the VC-dimension: the original statement of Lemma 4.1 says that the constant e, hidden in the O-)) notation, depends on (X, R),, but this is vacuous in our setting as (X, R.) is the entire problem instance. We show that (d) Ollog n) suffices, and provide proof in [.2 completeness.
Lemma 3.13. Let (X, R) be a range-space with [X] - n, | - m with dual VC-dimension most d. Then there exists a spanning tree T weight (T) Ommn!-1/6 1-/d log" n).
Proof. Let Ao = =X Consider the following process initialized at = O. By Lemma 3.1 there exists distinct Ii; yi E A; where the number of ranges in R crossing (at;, ys) is [(m|
1/ log n).
Iteratively letting A3+1+ + A; \ ay constructs a spanning tree T with weight at most
" Σ0(m - -)-- log (n - -)) S m log² "
J"" (==ddx ddr = O(mn' 1 log" n)-
We extend I Lemma 3.13 to corrupted VC-dimensions by converting the tree to single line of vertices, so that any single corruption minimally affects the number of crossings.
For instance, suppose X = [ra]. R is multiset of m empty ranges (corresponding to an X n zero matrix M), and the spanning tree is a star with E X at the center. If the corruption adds to each empty set in R (equivalently. turning the first column of M to an all-I-column), this fits into the definition of the dual having corrupted VC-dimension. This is because each set of (X, R) is corrupted by only one element, and thus in the dual set system each element is corrupted by adding it to one set.
After corruption, the number of crossings of each tree edge is (m) as 1 in each of the m sets, but none of the other elements in X are in any set. As the tree has n- edges, each connecting to another element of X, the tree has (mn) crossings in total. If, however, the tree was single line, the cor- ruption would affect at most 2 edges, and the total number of crossings would only increase by ((m) rather than (m We convert the tree to a single line in Lemma 3.14 proven in Appendix B.2
Lemma 3.14. For range space (X, R), |X| tation π E Sn such that the weight of the corresponding spanning tree T (which is just the line (1), T
with spanning tree T, there exists permu-
is at most twice that of
Proof of Theorem 3.7 Suppose M = + ST E (0, 1)mm has corrupted VC-dimension < d, where L E {0, 1 has VC-dimension d and S E {-1,0, 1 has at most -nn--//d) non-zero entries per column. and S exist by definition of corrupted VC-dimension.
Let (X, R) be the set system induced by L (i.c., each row of L is the indicator vector of a set in R with |R = m), by L having VC-dimension Σ d, (X, R) has dual VC-dimension V d. By Lemma 13 (X, R) has a spanning tree T with wTT S 1-/d log" n). Then, by Lemma 3.14, there exists a spanning tree T which is a line with weight at most (mm 1-1/d log n). Let (X, R.)) be the range space of M. 7' has the same weight as (X, Rc) as (X, Rt), excluding crossings due the corruption. For range E Re, we count the number of new crossings it incurs due to the corruption: an edge (z, y) only has new crossing for range E R. if x or y was corrupted in r. Since each x E X has at most 2 incident edges in T" (since it is a line) each corruption to r causes at most new crossings. Since the total number of corruptions is bounded by Omm" I we have w((T') < O(m log2 n) and T' is a llaablled spanning tree for M, as X = [n] are the column indices and the number of crossings for an edge (a., y) is the number of entries where M,, and M, differ. Since the MST has lower weight, its weight is at most O(mn' 1-/d log" n).
We can now put everything together to prove Theorem Theorem 1.3. (Static Online Matrix-Veche Multiplication). If a matrix M E (0, 1mmxn has corrupted VC-dimension d, then after an Õ(mm) -time preprocessing, there is a data structure D that can compute Me for any E 12th in Ö(mm 1-1/d + m) time, with high probability.

---

Proof. Preprocess M by constructing A-labeled spanning tree T for M via Theorem 3.6 in O(m)) time. Given R", pass and T' to the algorithm of Lemma 3.3 It returns My in time Ö(m + n n+ weight(T)). By Theorem 3.7 the MST of M has weight at most O since M has corrupted VC-dimension at most d. Since T is a Ollog n) approximation of the MST, answering query takes O(nm!-1/d + m) time.
3.3 Dynamic Matrices
At last, we outline how to handle matrices M that receive updates over time, i.c., Theorem 1.4 Theorem 1.4. (Dynamic Online Matrix- Vector Multiplication). Given matrix M E {0. mmxn, there is data structure DD with (m)) preprocessing time that supports row and column updates (insertions/dellttins)) to M in (()) and (m)) time, respectively. Upon querying D with vector v E IR", it outputs Me in Onn--11ja + m) time, with high probability, where d' is the largest corrupted VC-dimension of M throughout the history of its updates.
We sketch how to handle column insertions: Let M be the current matrix. We split it into smaller matrices M M()) ...y ( where each ( contains at most 2 columns of M. When new column is inserted to M, we insert that column to ( When any ( contains more than columns, then all its columns are inserted to ( and M is reset to an empty matrix. Thus, any ( receives new columns at most once every iterations to M. When an M receives new columns, we initialize a new matrix-vector multiplication data structure (Theorem 1.3) it. This takes (m22) time, but amortizes to ((m) time per insertion M since it only happens at most once every 2 insertions. This yields an amortized time log Õ(m) = Ō(m) time to maintain all ( for O, O,..., log n. To answer a matrix-vector multiplication query Mr, we split into vectors ((0) ..... (logn) such that Mr = Eler R (()))(()) For the time complexity, note that each ( is submatrix of M. Thus, the the time complexity needed to multiply vector by M is bounded by O(mm!11/d m..
We ignore column deletions to M until M is reinitialized: simply set vy = 0 for the columns that should have been deleted. We can handle row updates to M in a similar way, by splitting the matrix again into log matrices, each containing at most 2' rows. The full proof is given in Appendix B.3
4 Conclusion
We study the structural complexity matrix- vector multiplication. We propose theoretical frame- work to study heuristic algorithms that have achieved tremendous practical success. Building on the VC-dimension literature, we propose the notion of a corrupted VC-dimension and provide structural characterizations. We show that if a matrix M E (0. (0,1)ma mmn has corrupted VC-dimension d, then its matrix-vector product Me be computed in O(mm1-1/4 + m) time, providing polynomial speed-ups over existing methods. Moreover, our algorithm maintains updates to M in ((m) and (()) time, leading to the first Ō(n=-c)-time algorithms for maintaining high-accuracy estimates for Laplacian solvers, effective resistance, and triangle detection in dynamic graphs.
Limitations. While we show subquadratic runtimes in non- non-Boolcan Boolcan matrices with bounded Pollard pseudodimension, we believe that the linear dependence of the number of distinct values T in the runtime suboptimal and should instead be logarithmic. Finally, without matching lower bounds, we cannot verify whether the 2-1/// scaling with respect to the VC-dimension is optimal.
Societal Impacts. This work is foundational in nature. As such, while it enables more efficient computation in iterative algorithms, it is not tied to any specific applications or deployments.
Acknowledgements
This work was supported by NSF Grants DMS 2202961 and CCF 2338816. We also express our thanks to Ce Jin, Andrzej Lingas, Albert Weng, Jesper Jansson, Shunhua Jiang, Xiaobai Sun, Elia Gorokhovsky, and Jingtong Sun for insightful discussions.
10

---

References
Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. IEEE 57th Annual Symposium on Foundations of Computer Science, 2016.
Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434 443. IEEE Computer Society, 2014. doi:
2011..,, URL Uttpttss: //dotps:/ddi.oeoo org/10. 10. 1109/FOCSS 2014.001 .53
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, and Raghu Meka. New graph decompo- sitions and combinatorial boolean matrix multiplication algorithms. STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.
Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pages 335-344, 2016. doi: 10.1109FOCS.2000C 2016.444
Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph clustering using effective resistance. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 2017. http:ttts:/// org/ abs/ 1111//111.... 06530
Josh Alman and Virginia Vassilevska Williams. OV graphs are (probably) hard instances. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPles, pages 83:1-83:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2020. doi: 104420//IPICSSIICS..2D0. 2020....
Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In Sandy Irani, editor, 61st IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 541-552. IEEE, 2020. doi: F1L11////OOSS67002200000000
Noga Alon, Shay Moran, and Amir Ychudayoff. Sign rank versus VC dimension. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 47-80, Columbia University. New York, New York, USA, 23 26 Jun 2016. PMLR.
João N. F. Alves, Samir Moustafa, Siegfried Benkner, Alexandre P. Francisco, Wilfried N. Gansterer, and Lufs M. S. Russo. Accelerating graph neural networks with a novel matrix compression format, 2024.
Emile Anand and Sarah Liaw. Feel-good thompson sampling for contextual bandits: markov chain 15290
monte carlo showdown, 2025. httphhps:://axxi.rrrr//aaa/////a
Emile Anand and Guannan Qu Efficient reinforcement learnnn presence of local agents scale. arXiv preprint arXiv:2403.00022, 2024.
learning for global decision making in the
Emile Anand and Chris Umans. Pseudorandomness of the sticky random walk. Caltech Thesis http:///.wwrr.abbb.....111.
Archives, 2023. URL htthttt:::/
Emile Anand, Ishani Karmarkar, and Guannan Qu. Mean-field sampling for cooperative multi-agent reinforcement learning. ArXiv, abs/2412.00661. 2024a.
Emile Anand, Jan van den Brand, Mehrdad Ghadiri, and Daniel J. Zhang. The Bit Complexity of Dynamic Algebraic Formulas and Their Determinants. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 20244,, volume 297 of Leibniz International Proceedings in Informatics (LIPles), pages 10:1-10:20 Dagstuhl, Germany, 2024b. Schloss Dagstuhl Leibniz-Zentruu für Informatik. ISBN 978-3-95977-332-5. doi: 10.4223/L.PPIcsICCA. 1...2..2..2...11 10. URL https //drops. dagstuhl dddrogg.dgggtuh...ceaimiiieeeeee sttttteesdddcmennnt/ee 10. 4230/LIPICs. ICALP 2024.10 10
Rosa Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine learning, 63(2):161-182, 2006.

---

P. Assouad. Densité et dimension, Annales de I'Institut Fourier, 33:233- 2202,22222111 1983.
Emo Welzi B. Chazelle. Quasi-optimal range searching in spaces of finite vc-dimension. Discrete & computational geometry, 4(5):467-490, 1989. URL UKL/attp///eumml.oo///oo///////
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension
and pseudodimensson bounds for piecewise linear neural networks. Journal of Machine Learning
Research, 20(63):1-17, 2019. http:///:/ www.aarrrrrpapppp/peeeeee pttppppp///////-111222 http://///.aaaaaaooooop/////////
.1m.mmll
Julien Basch, Sanjeev Khanna, and Rajeev Motwani. On diameter verification and boolean matrix multiplication. Technical report, Stanford University, Stanford, CA, USA, 1995.
Andreas Björklund and Andrzej Lingas. Fast boolean matrix multiplication for highly clustered data. Frank Dehne, Bürg-Rüdiger Sack, and Roberto Tamassia, editors, Algorithms and Data Struciures, pages 258-263, Berlin, Heidelberg. 2001. Springer Berlin Heidelberg. ISBN 978-3- 540044634-7.
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li, Aline Parreau, and Stéphan Thomassé. Identifying codes in hereditary classes of graphs and vc-dimension. SIAM Journal on Discrete Mathematics, 29(4):2047-2064, January 2015. ISSN 1095-7146. doi: 10. 1777779997879x
Jan van den Brand, A deterministic linear program solver in current matrix multiplication time. In SODA, pages 259-278. SIAM, 2020.
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In FOCS. pages 456-480. IEEE Computer Society, 2019a. URL /ttxxva.vvvv///////////////a.av/ org/ org/pdf/ 1905. 05067. pdf
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. Dynamic matrix inverse: Im- proved algorithms and matching conditional lower bounds. In 2019 IEÉE 60th Anmual Symposium on Foundations of Computer Science (FOCS), pages 456-480. IEEE, 2019b.
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time. In Proccedings of the 52nd Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA. June 22-28 26, 2020, pages 775-788. ACM, 2020. doi: 10. URLpttpss //dl. acm. org/ /ttd//di////////// 10. 11 1145 3384330
1145/3357713.3384300
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and é, ei)rregressoon in nearly linear time for dense instances. In STOC, pages 859-869, ACM, 2021.
Jan van den Brand, Sebastian Forster, and Yasamin Nazari. Fast deterministic fully dynamic distance approximation. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pages 1011-1022. IEEE, 2022. doi: 10. 1109/FOCS54457.22222 2002000044......000009.. URL URL https://doi.. orgo 10. 1009//0CS54457 2022 00099
Jan van den Brand, Sebastian Forster, Yasamin Nazari, and Adam Polak. On dynamic graph algorithms with predictions. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages SIAM, 2024. doi: 10. 117/1 71711.9716611 11779111979
Diptarka Chakraborty, Lior Kamma, and Kasper Green Larsen. Tight cell probe bounds for succinct boolean matrix-vector multiplication. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1297-1306. ACM, 2018 doi: 01155/188745.33 887.333..33......
10.1145/3188745.33
Shreyas Chaudhari, Srinivasa Pranav, Emile Anand, and José M. F. Moura. Peer-to-peer learning dynamics of wide neural networks. IEEE International Conference on Acoustics, Speech, and Signal Processing 2025, 2024. UtL.pttts:://axxt org/ abs/ abss//409 2409. 15267
Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance queries over dynamic interval graphs. Comput. Geom, 122: 102103, 2024. doi: 1016/ COMGEO.2024.000 102103.. URL http::ttp://et org/ 10. 1016/j comgeo. 2024. 102103.
12

---

Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. J. ACM, 68(1):3:1-3:39 2021. Announced STOC' 19.
David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In Leo Liberti, editor, 22nd International Symposium Experimental Algorithms (SEA 2024), volume 301 of Leibniz International Proceedings in Informatics (LIPles), pages 8:1 1:200, Dagstuhl, Germany, 2024. Schloss Dagstuhl Leibniz-ZZnntrum für Informatik. ISBN 978-3-95977-325-6 doi: 10.4200/.PPIcs.SAA.200
Christophe Crespelle. Fully dynamic representations of interval graphs. Theor, Comput, Sci., 759: 14-49, 2019. doi: T0..016/..
Emilio Cruciani, Sebastian Forster, Gramoz Goranci, Yasamin Nazari, and Antonis Skarlatos. Dy- namic algorithms for-center on graphs. In SODA, pages 3441-3462, 2024.
Mohsen Dehghankar, Mahdi Erfanian, and Abolfazl Asudeh. Optimized inference for 1.58-bit Ilms: A time and memory-efficient algorithm for binary and ternary matrix multiplication. arXiv preprint arXiv:2411.0633 2024.
Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Catalan structures and dynamic program- ming in h-minor-free graphs. Journal of Computer and System Sciences, (815):606-1622 2012. ISSN 0022-0000. doi: https//doi..or// 10. joss
JCSS Special Issue: Cloud
Computing 2011.
David Durfee, Yu Gao, Gramoz Goranci, and Richard Peng. Fully dynamic spectral vertex sparsifiers and applications. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 914 925. ACM, 2019. doi: 10.1145/3313276.331633
David Eppstein. Graphs with bounded radial order are small. In Proceedings of the 3rd Annual European Symposium on Algorithms (ESA), volume 979 of Lecture Notes in Computer Science, pages 392-404. Springer, 1995. doi: 00.100733-540-033
60313-1_165.
Vissarion Fisikopoulos and Luis Penaranda. Faster geometric algorithms via dynamic determinant computation. Computational Geometry, 16,1-16,22000 2016.
Peter Floderus, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, and Dzmitry Sledneu. 3d rectangulations and geometric matrix multiplication. Algorithmica, 80(1):136 154, January 2018. ISSN 0178-4611 doi: 10.10077.00453--16--22---3 URL httpt:///oo.... htt////...rg/....00000111 1007/
0194533016-024777
Dimitris Floros, Nikos Pitsianis, and Xiaobai Sun. Algebraic vertex ordering of sparse graph for adjacency access locality and graph compression, 2024.
Gudmund Skovbjerg Frandsen, Johan P. Hansen, and Peter Bro Miltersen. Lower bounds for dynamic algebraic problems. Inf. Comput., 171(2)3333334) 2001. doi: 10. 1000//0CO.2000 2001.3004
Leszek Gasieniec and Andrzej Lingas. An improved bound on boolean matrix multiplication for highly clustered data. In Frank K. H. A. Dehne, Jörg- Rüdiger Sack, and Michiel H. M. Smid, editors, Algorithms and Data Structures, 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30-3000000 August I, 2003, Proceedings, volume 2748 of Lecture Notes in Computer Science, pages 329-339. Springer, 2003. doi: 10.1007/978-3- 3-540-45078----8 _
Arpita Ghosh, Stephen Boyd, and Amin Saberi. Minimizing effective resistance of a graph. SIAM Review, 50(1):37-66, 2008 doi: 10. 1137//50045552..
Raphael Clifford. Allan Gronlund and Kasper Green Larsen. New unconditional hardness results for dynamic and online problems. In Proceedings of the 2015 IEEF 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, page 1089-1107, USA, 2015. IEEE Computer Society. ISBN 978 147738118, doi: 10. 10.0000/00..
Sariel Har-Peled. Approximating spanning trees with low crossing number. ArXiv, abs/0907.1131. 2009. URL https::///// //api www.seeesaaootttneoo. wwtp:ollaaorrrororrooeeeeo www.oorgg//orrrrioooooooo 15811439
13

---

D Haussler and E Welzl. Epsilon-nets and simplex range queries. In Proceedings of the Second Anmual Symposium on Computational Geometry, SCG '86, page 61-71, New York, NY, USA. 1986. Association for Computing Machinery. ISBN 089791 1946. doi: 10.1 10.1145/10515.10522
URL https://doi http:///ooo.rrg/10... 1145/105151111 1 10522
Monika Henzinger and Stefan Neumann. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium Algorithms (ESA 2016), volume 57 of Leibniz International Proceedings in Informatics (LIPlcs), pages 48: 1 18: Dagstuhl, Germany, 2016. Schloss Dagstuhl Leibniz- Zentrum für Informatik. ISBN 978-3- 11183-3-9977-15--6
doi:
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC '15, page 21-30, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450335368 doi: 10.1 145/2746539.27466099
Monika Henzinger, Andrea Lincoln, and Barna Saha. The complexity of average-case dynamic subgraph counting. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference Alexandria, VA, USA, January 9 12, 2022, pages 459-498. SIAM, 2022. doi: 10.1 7T111377998811111777733
Monika Henzinger, Barna Saha, Martin P. Seybold, and Christopher Ye. On the complexity of algorithms with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, 087:62:1-62:255 2024. doi: 1044230/
Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1(3):209-215, 1979. ISSN 0166-218X. doi: https://doi.org/100 1016/ 0166-218X(79)90044411
Bingbing Hu and Adam Polak. Non-boolean omv: One more reason believe lower bounds for dynamic problems. arXiv preprint arXiv.2409.15970, 2024.
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving SDP faster: A robust IPM framework and efficient implementation. In 63rd IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO. USA, October 31 November 2022, pages 233-22223 244. IEEE, 2022. doi: 10. 10.1109/OCC55445722222 2022200009.....00022..,.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the Thirtieth Anmual ACM Symposium Theory of Computing, STOC '98, page 604-613, New York, NY. USA, 1998. Association for Computing Machinery. ISBN 0897919629. doi: 10.1145/276698.2766
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In FOCS, pages 910-918, IEEE, 2020a.
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games, and its applications. In STOC, pages 943-953. ACM, 2020b.
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general lps. In STOC, pages 823 232. ACM, 2021.
Shunhua Jiang, Bento Natura, and Omri Weinstein. A faster interior-point method for sum-of- squares optimization. In ICALP, volume 229 of LIPlcs, pages 79:1-79:20. Schloss Dagstuhl Seibniz-Zentrum für Informatik, 2022.
Shunhua Jiang, Binghui Peng, and Omri Weinstein. The complexity of dynamic least-squares regression. In 64th IEEE Annual Symposium Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1605-1627. IEFE, 2023. doi: 10. 109/ FOCS57990.2023.000 0.0997.
14

---

Ce Jin and Yinzhan Xu. Tight dynamic problem lower bounds from generalized bmm and omv. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2022, page 1515-1528, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392648, doi: 10.1 145/3519935.3520036
Adam Karezmarz and Da Wei Zheng. Subquadratic algorithms in minor- minor-free digraphs: (weighted) distance oracles, decremental reachability, and more. arXiV, 2024.
N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):
373-396, 1984.
Toni Maria Klein, Christine Blome, C. Elise Kleyn, Curdin Conrad, Paul G. Sator, Mona Ståhle, Kilian Eyerich, Marc Alexander Radtke, Christine Bundy, Myriam Cordey, Christopher E. M. Griffiths, and Matthias Augustin. Real-world experience of patient-relevant benefits and treat- ment satisfaction with apremilast in patients with psoriasis: An analysis of the appreciate study. 155/://1135550000222200
Dermatology and Therapy, 12(1):81-99 2022. doi:
Tuukka Korhonen, Wojeiech Nadara, Michal Pilipezuk, and Marek Sokolowski. Fully dynamic approximation schemes on planar and apex-minor-free graphs. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithmss SODA 2024, Alexandria. VA. USA, January 7-10, 2024, pages 296-313. SIAM, 2024. doi: 10.1137/1.988161199979999
Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians fast, sparse, and simple. In FOCS, pages 573-582, IEEE Computer Society, 2016.
Kasper Green Larsen and Ryan Williams. Faster online matrix-vector multiplication. In Proceedings of the Twehty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA '17 page 2182-2189, USA, 2017. Society for Industrial and Applied Mathematics. URL https:///ppbb: siam wia..oog/ www.ooog//o//10/0//o/ 1 9781611977782.. 142
Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear programming. In FOCS, pages 230-249. IEEE Computer Society, 2015.
Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In COLT, volume 99 of Proceedings of Machine Learning Research, pages 2140-2157 PMLR, 2019.
Edo Liberty and Steven W. Zucker. The mailman algorithm: note on matrix-vector multiplication. Information Processing Letters, 109(3):17--182, 2006. ISSN 0020-0190. doi: https://doi.org/ 100. 1016//. 2016/..ipl.2008.009 09.088............
Yiheng Lin, James A Preiss, Emile Timothy Anand, Yingying Li, Yisong Yue, and Adam Wierman. Online adaptive policy selection in time-varying systems: No-regret via con- tractive perturbations. In Thirth-seventhh Conference on Neural Information Processing Sys- tems, 2023a. URL https://proceeddiiie (tw.2oofff77221118eee8822226666
www.riiss.cccppppppe fiwes/illpppeee wttpr/fiileeeelile/// /ppp/pppp////////leeeee Confereeee pdf
Yiheng Lin, James A Preiss, Emile Timothy Anand, Yingying Li, Yisong Yue, and Adam Wierman. control via online adaptive policy selection: No regret via contractive per- turbations. In ACM SIGMETRICS, Workshop on Learning searning-angmenti augmented Algorithms: Theory and Applications 2023, 2023b.
Yiheng Lin, James A. Preiss, Fengze Xie, Emile Anand, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online policy optimization in unknown nonlinear systems. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 1475-3522 PMLR, 30 Jun 03 Jul 2024. URL
mir. www.ppress/vvee w2sts////22/11222...m html
Andrzej Lingas. A geometric approach to boolean matrix multiplication. In Proceedings of the 13th International Symposium on Algorithms and Computation, ISAAC '02, page 501-510, Berlin, Heidelberg, 2002. Springer- Verlag. ISBN 3540001425.
Yang P. Liu. On approximate fully-dynamic matching and online matrix-vectes multiplication, 2024.
15

---

Alane Marie de Lima, Murilo da Silva, and André Vignatti. A range space with constant vc dimension for all- aal-sairs shortest paths in graphs. Journal of Graph Algorithms and Applications, 27:603-611 619, 08 2023. doi: 10.71 2555/aaa.00666666
Jifí Matoušek. Spanning trees with low crossing number. RAIRO Theoretical Informaties and Applications Informatique Théorique et Applications. 25(2):103-122 1991.
Jifí Matoušek. Leclures Discrete Geometry, volume 212 of Gruduate Texts in Mathematics. Springer, 2002. ISBN 978-0-337--55373-0 doi: 00.1007/978-1-461-000333
Elchanan Mossel and Christopher Umans. On the complexity of approximating the ve dimension.
Journal of Computer and System Sciences, 65(4))660-671, 2002. ISSN 0022-0000. doi: https:
httg//..111//0022220 (000(0))00022-3, URI. http:/tttp//eeeeelllorr ieee org/ document/
933889
Special Issue on Complexity 2001.
Theodore S. Motzkin. Evaluation of polynomials and evaluation of rational functions. Bulletin of the American Mathematical Sociery, 57(2):163-16) 1951.
Riley Murray, Venkat Chandrasekaran, and Adam Wierman. Newton polytopes and relative entropy optimization, Foundations of Computational Mathematicx, 21(6): 2021. doi: 10. 1007/
Tung Nguyen, Alex Scott, and Paul Seymour. Induced subgraph density. vi. bounded ve-dimension. wrg/abs////ge.e 2212. 15572
arXiV, 2024.
Vadim Olshevsky and Amin Shokrollahi. Matrix- product for confluent cauchy-like matrices
with application to confluent rational interpolation. In Proceedings of the Thirty-Second Annual
ACM Symposium on Theory of Computing, STOC "00, page 573-581, New York, NY, USA, 2000.
Association for Computing Machinery. ISBN 1581 131844. doi: 10. 10.1145/3353055333588) URL
https://dl.. acm. do1/10.1111111/// 1145/335303 0rg./bo3/10..115//35555 335380
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking:
Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999. URL http:
//ilpubs. stanford..dooooooo edu/422/
Victor Y. Pan and Elias Tsigaridas. Nearly optimal computations with structured matrices. In Proceedings of the 2014 Symposium SymbbolicNummert Computation, SNC '4, page 21-30, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 978 1450329637. doi: 10.1 10.1145/2631948.2633 2.....66315... URL /ttp:/tss://iiiorr/////// 1ttp://1.1111/121119 2631954
James Renegar. Condition numbers, the barrier method, and the conjugate-gradient method. SIAM Journal on Optimization, 674):879- 1996. doi: 10. 00.1137/110522224442755522 URL https
//doi wrtg//..11///111.... /tt..0111///11102222447777555550
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by pack-propagating errors. Nature, 323(6088) 1986. doi: 10. 1038/3333333....
Shai Shaley-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge, UK, 2014. ISBN 978-1-107-05713-5.
Hans Henrik Brandenborg Sørensen. High-performance metrix-vector multiplication on the gpu. In Michael Alexander, Pasqua D' Ambra, Adam Belloum, George Bosilea, Mario Cannataro, Marco Danelutto, Beniamino Di Martino, Michael Gerndt, Emmanuel Jeannot, Raymond Namyst, Jean Roman, Stephen Scott, Jesper Larsson Traff, Geoffroy Vallée, and Josef Weidendorfer, editors, Euro-Par 2011: I: Purallel Processing Workshops, pages 377-386, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-297377-3 URL httph::/pps:ii httts:://iinksssiingerr com/ 072-3---2-2297772-222
springer
Chapter/10. /10./10.00
Daniel A. Spielman and Shang-Hua Teng. Nearly- -inear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In STOC"04: Proceedings of the 36th Annuul ACM Sympoxium on Theory of Computing, pages 81-90. ACM, 2004. URL U htttps://///t acm. acm.org/ doi/10. 1145/ 11111111//1112220000
16

---

Ali Tizghadam and Alberto
On robust traffic engineering in transport networks. In IEEE GLOBECOM 2008 2008 IEEE Global Telecommunications Conference, pages 1-6, 2008. doi: 10.1 10.1109/GL.OCCM 200.. ECP.456.
Pravin M. Vaidya. Speeding-up linear programming using fast matrix multiplication (extended abstract). In FOCS, pages 332-337. IEEE Computer Society, 1989. /RL/httpp:/ieeeexplloo
leee. org/ doccment/ /33/9///////99///// 63499/
Santosh S Vempala, Ruosong Wang, and David P Woodruff. The communication complexity of optimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1733-1752. SIAM, 2020.
E. Welzl. Partition trees for triangle counting and other range searching problems. In Proceedings of the Fourth Annual Symposium on Computational Geometry, SCG 888, page 23-33, New York, NY, USA, 1988. Association for Computing Machinery. ISBN 0897912705. doi: 10.1 10.11497739..7733997
Emo Welzl, On spanning trees with low crossing numbers. Lecurr Notes Computer Science, 1992.
htt.https///// http:///wwwwmddmmmmmmmm//mmmm numdam. org/ article/ _TA_AIAAAA11111111 11___1991___220 25_ 103_0.000000 pdff
Ryan Williams. Matrix-vector multiplication in sub-quadratic time: (some preprocessing quired). In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, page 995-1001 USA, 2007. Society for Industrial and Applied Mathematics. ISBN 9780898716245.
Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Anmual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645-654. IEEE Computer Society, 2010. doi: 10.11099/OCS.200000 URL https://dooi org/ 10. 1109/FOCS 2010.67
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In SODA, pages -8332. SIAM, 2024. URL https
//epubs. siam. wtw.:.aw......o..o/.o. wwt/ 111771.988161117711122.338
Hakan Yildiz and Subhash Suri. On klee's measure problem for grounded boxes. In Proceedings of the Twenty-Eighth Annual Symposium Computational Geometry, SoCG '12, page 11 111-120, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 978 14453129999 doi: 10.1 (,11445/226122 255.:2222225022226 256.2261267 http:httts:///oi..oo
22446222210000222226887 2261267
17

---

Contents
Preliminaries for Supplementary Material
19
B
Online Matrix Vector Data Structure
19
B.
Static Online Matrix Vector Multiplication Data Structure
19
B.2
Existence Low Weight A-labeled Minimum Spanning Trees
................................
22
B.3
Dynamic OMv Data Structure
23
B 4
Extension Structured Non- Boolean Matrices
25
Applications
26
C.1
High-accuracy Dynamic Laplacian Solver
26
Effective Resistance
................................
27
Triangle Detection
28 ................................
Single-Source Shortest Paths and k-Center
28
D Characterization of matrices with constant VC-dimension
29
D.I Examples low VC-dimension matrices
30
Numerical Simulations
31
18

---

A Preliminaries for Supplementary Material
Notation. Let [n] = (I...., n). We use O(+) to hide constant factors, and Ō(-) to hide polylogarith- mic factors. Let || ||1 denote the & (Manhattan distance). For any matrix M. let M; and M., denote its i'th column and i'th row (respectively). For a set V we write M E m@ for the m x [V| matrix where we can index columns by x V, i... M, weight of z is the number of non-zero entries of z also denoted by nnz(x). For Boolean vectors r, E {0, 1}", the Hamming distance between x: and y is given by | - y Finally, for any vector x E R and positive definite matrix L E R define the L-induced norm of x by ||>||1_ = Vx Lx.
R". For any vector X E R", the Hamming
VC-Dimension of Range Spaces. A range space (also called set system) is pair R = (X, R) where X is set and R is set of subsets of X. Let II (AA) {A {Anr:r :n:r-- E R). The VC-dimension of is given by VC(R) = max [|S] S C X and [S) = 21 The primal shatter function of R is given by x ((m) = max [T [A] A X, = m] for m 2 0. Let B be a set of ranges R. Then, let x
S Xand C is not crossed by any range in Q} and let I1' (B) be maximal. Then, for m 2 0, the dual shatter function 'T" of the range space is given by
{C
x ('m) = max[[1l; (B) B C R. [B] = m].
VC-Dimension of Matrices. Any matrix M E {0, 1 corresponds to a set family given by FM = {{i M, = 13 : E [m]]. i.e. consider each row of M as the indicator vector of some set. Through it, we can encode M by the range space Ru = ([n].
Then, the VC-dimension of M defined as the VC-dimension of RM. Here, subset S of the columns of M is said to be shattered if each of the 2 many 0/1 strings appears in some row in the restriction of M to the columns in S. Then, the VC-dimension of M the maximum size of a shattered subset of the columns of M. Moreover, the VC-dimension dmn. of matrix M E (0. 1] jmxx satisfies 1 S dmm. S logm.
Pollard Pseudodimension of Matrices. For a family of functions mapping X to Y. the Pollard pseudodimension of F, denoted by Pdim(FF, is the VC dimension of the set system (X x Y, (L(,((, 3) f(x) y} I E FJ).
For a real matrix M, define the pseudo-diment the rows of M functions and taking the gseudo-dimension of the resulting class of functions. Specifically, if M is an m x matrix, for each i E (I.....m), define JM,:: [1,...,n} + IR by [(, Mij, and let Pdim(M)
of M, denoted by Pdim(M) by thinking of
(/M,: : E (1,-..,m) m]))-
B Online Matrix Vector Data Structure
In this section we prove all the intermediate lemmas required for our first two main results on subquadratic online matrix-vector multiplication. The proof that combined the technical lemmas was already given in Section 3
Theorem 1.3, (Static Online Matrix- Vector Multiplication). If a matrix M E 10,1)mxn has corrupted VC-dimension d, then after an ((mm)-time preprocessing, there is a data structure D that can compute Me for any I in ((m) + m) time, with high probability.
Theorem 1.4 (Dynamic Online Matrix- Vector Multiplication). Given matrix M {0,1) 1)mxn, there is a data structure D with (mm) preprocessing time that supports row and column updates (insertions/delltions)) to M in (nn) and Õ(m) time, respectively. Upon querying D with vector E IR", it outputs Me in Omam!-1/a + m) time, with high probability. where d' is the largest corrupted VC-dimension of M throughout the history of its updates.
B.1 Static Online Matrix Vector Multiplication Data Structure
Definition 3.1 (A-labeled spanning tree of matrix M). A A-labeled tree is tree T (V, E) with some explicit root where each edge E E is directed away from and labeled by vector A. E Rd We say T is A-labeled spanning tree for matrix M E Tgmx ifM, = =0 for root and for all edges (i,j) E E we have A..j = M, M,.
Definition 3.2 (Weight of a A-laheled spanning tree). For any A-labeled spanning tree of M denoted by T with directed edge-set set E, define weight(T)) Eeet nnz( (n))
19

---

Algorithm 1 Online Matrix-vector multiplication (given A-labeled tree of M')
Require: Input matrix M 10,m, and a A-labeled tree of M denoted by T and rooted Input vector E RR.
Require:
Initialize: Φ 0m
4, M v
Run DFS on 7 from root r. Whenever DFS visits a vertex via some edge (y. x), then set o Ly + 2
Return +
Lemma 3.3 (Björklund and Lingas 2001 of M E {0, 1] Ij and vector R
Alves al. 2024 Given A-labeled spanning tree T
we can compute Mr in O( (Twiight(T) + m) time.
Proof. Consider Algorithm | which takes as input M E {0, [0,1)m* A-labeled spanning tree of M (denoted by T), and vector E R".
We inductively prove that = Me over the number visited vertices. This true when only one vertex is visited, that the root r and by definition 4, (Mc),. For the inductive step, assume DFS visits the (k + 1)st vertex r. Let be the parent of the vertex, then the algorithm assigns
4 Dy + A y
(Mu), + (Mr M2)U
(Mv)..
Here by is already computed since it among the first k visited vertices.
Runtime analysis. Let 6,, be the number of non-zero entries in A., for all (i,j) E E(T). Initializing the vector & and populating its first element 4 takes On + m) time. The cost of populating the remaining entries proportional to the number of non-zero entries in each A2,y, since we can store each via sparser representation of only its non-zero entries and use this to compute A v in time (6 Thus, the total time complexity is O(Σ (a.))EEEE 62.z) = O O(weight(T)) Hence, the runtime of Algorithm] is (Te + n + m). proving the lemma.
When the spanning tree constructed over the columns M, we run a different algorithm. The following matrix N is defined based on the spanning tree. We will prove (i) that multiplying vectors with N can be done efficiently (Lemma B.2). and (ii) that N = M (Lemma B.3 Combining the two then yields Lemma 3.4
Definition B.1 (Path-A matrix N(T)), Given A-labeled subtree T (V, F)) with root r, define the path-A A matrix N(T) E m such that for V,
T
Σ
A
cEP(r-aa
Here, P(r -> u) denotes the edges of the unique (since T is acyclic) directed path from r to u. Lemma B.2. For Allabeled tree EV, and a vector v E RY, let E E with (gy.)) =
ELEV(T)) Uo. where To is the subtree rooted at e E V. Let A R be the matrix with columns being the labels of tree T. Then Ao = (T)
Proof. By the definition of (()), we have
T
(T)
By
yEV
Σ
Σ
A U
VEV cEP(r-h))
Now consider how often any one edge e shows up this sum: an edge e (x) is in P(r - y> and only if is ancestor of (or y 2) (or, in other words, if is a descendant of z (or y 2)).
20

---

This condition can be written as E T3. Thus we write the sum
Σ Σ
Uy = Σ
Σ
A
U2
yEV cEP(r-U)
(0,2)E
DET,
Σ
A
(RAA)RR
yET,
Σ
Z.
(aN))E
which proves the claim.
Lemma B.3. Let be A-labeled spanning tree of M where the root r of T has M, = then N M.
Proof. We prove this by induction over the width of M.
Base Case. For width 1, T is just the root r, so N(T) Ū M.
Inductive Step. Suppose the statement holds for matrices of width and now have matrix M of width n. Let V be the leaves of T. Let T" be the tree T with these leafs removed, and let M' E {0, 1] (V)))))) be matrix M with all columns corresponding to L removed. Then for any y NEVIL
My
N
where equality (1) uses the induction hypothesis and equality (2) uses the fact that any path in the leaf-removed tree 7" also exists in T.
For any y E L let be its ancestor in T. Therefore, $ L. Then, we have
( = N + Az.y
N(T") + Az.y
=M, + A...
= =M, + (M, - M,) = My
where equation Jses the fact that the path from root r to y is a path from root r to z with one extra edge (z, y). Equation 2 uses the fact the path from to in 7 also exists in 7", and finally equation follows by the induction hypothesis. Together, they prove the lemma.
Lemma 3.4. Given A-labeld spanning tree T of M E (0,1)"xx and a vector E R", there is an algorithu that can compute Mu ((weight(T) + n + m) time.
Proof. Algorithm:
We compute ( via Lemma B.2
which requires us to compute the vector o e IR with ( E.ev(T)) ys for (y, c) E where T. the subtree of T rooted at c. This can be done in ((n) time via simple "dynamic programming on trees" algorithm: For any e E V, let C be its children.
Then,
( =
Σ
U1
*EV(T.)
+
Σ
Σ U2
aEC sEV(EV
= Uee + Σ ((caa)-
aEC
21

---

So we can compute & in (n) by starting at the leaf-edges, then propagating the sums up towards the root. At last, multiply Âø in ((weight(T)) time that is the number of non-zeros in A (which the matrix consisting of the tree labels as column-vectors)
Without loss of generality, assume that for root r of tree we have M, Ô. Otherwise, append 0-column to M, and add edge (n + 1, to with label Apt1, = M, M,- M,. and make n + 1 the new root of T. This increases the tree weight by at most m, resulting in an additive (m) in the time complexity.
Correctness.
Append another entry to o so that the dimensions match and Mu is well-defined. By Lemma thus have N(T) MM..
B.3 we
B.2 Existence of Low Weight A-labeled Minimum Spanning Trees
We first provide proof of Lemma 3.11 (Lemma 4.1 of Welzl 1988 restated below for completeness.
Lemma 3.11 (Lemma 4.1 of Welz! 1988). Let (X, R) be runge space with dual VC-dimension at most d. For every A C X,, = 2 and every multiset Q of ranges in R with |Q] = m, there exists x + y E such that the number of ranges in Q crossing (x, y) at most O(mn 1// log" n).
For this, we introduce the notion of e-nets and a crucial proposition of Welzl 1988 and Haussler and Welzi 1986..
Definition B.4 (c-net), Let (X, R) be a range space and 0 S c c Let be a finite multiset of elements in X. Then, N S A is e-net of for
r R if LAnrl implies N.N + 0 for all r E R. [A]
Proposition B.5 (Welzll 1988 Proposition 2.4]). Let (X, R) be range space of VC-dimension Z and let < 6 S be a real number. For every finite multiset of elements in X, there is an e-nel N of A for R such that [N| <
8d log 8d
Lemma B.6 (Lemma 2.2 of Welzl 1988 (X, R) is range space of VCddimension d, then (X, R). where R {(r' Ur") (r' (r"") Irr, rd E R) has VC-dimension most Od d).
We are now ready to prove Lemma 3.11 which we adapt from Welzl 1988
Proof of Lemma 3.77 By the pigeonhole principle, sufficient to show the existence of subset N of Q such that (i) x ([[N] < n and (ii) if pair of elements {x, y) is crossed by more than dmn-1 11/d log ranges in Q, then {2.v} is crossed by range in N.
For X, let R2 fr R E r) and for xr X with x A y, let Ray be the of ranges in R that cross {x, 3). Since [R Rg x is the dual of (X, X R) has VC-dimension at most d by assumption. So by Lemma B.6 (R, [Ray xz y E X, + y}) has VC-dimension O(d log d).
Therefore, by Proposition B.5 for every e > 0 and every multiset Q of ranges in Rt there an e-net of Q for [Rzy xr y E X, x # y} with |N| < Oldlog d) log Oldlogd) Now, let e cdn - 1/d log where e cs some constant. Then, there is an e-net of Q of size at most
1/d
log (Oldlog d)
n//d cdlogn ) S 1/d
Od d)
edlogn
where c I (1). For large enough c, we can get small enough e such that ' ([cin!/d) < n. For some constant c, we thereby get a (cdn log n)-net of Q for the ranges Rzy with ([V] < n. This implies that there is pair of elements {x, crossed by more than ed|Q)n 1/d log n cl/m log ranges in Q. Finally, applying d < log n concludes the argument.
Lemma 3.14. For a range space (X, R), |X| = n with spunning tree T, there exists permu- lation π E Sn such that the weight of the corresponding spanning tree T" (which is just the line (11), T (2), (n)) (1)) is at most twice that T.
Proof. Enumerate all the ranges in R. by RI.... Rms where Ra (c: Mic 1} for i i [m].
22

---

The crossing number of R; in T counts the number of edges in T such that one endpoint of the edge in R and the other endpoint in [nl R, Suppose the spanning tree T on X has crossing number of K; for just R. and let w(T) >== K; be the weight of ' for R).
Perform DFS traversal T and write the in-order traversal I. We the permutation =(() I, for i E [n]]. Let 7" be the corresponding linear tree. In the worst case, this vertex path crosses R& 2x; times, that is because DFS uses each edge (x, y) of I'' twice: once when visiting y (going down one level in the tree) and once when it is done processing (DFS pops the current level from the stack).
Thus the total number of crossings wT") for the linear tree T" is w(') S Ei= 2kz (x(T).
B.3 Dynamic OMv Data Structure
In this section we give a black-box reduction from dynamic OMv to static OMv. the static version, we are given a matrix M to preprocess. This matrix stays fixed, while we receive an online sequence of vectors and must repeatedly compute Mu. In the dynamic version, we can inform the data structure about changes M. Specifically, we are allowed add/remove/change rows/columns of the matrix.
Using the reduction from dynamic to static, we obtain Theorem I.4
Theorem 1.4. (Dynamic Online Mairix- Vector Multiplication). Given matrix M E {0,1) there is data structure 'D with (mn) preprocessing time that supports row and column updates (insertions/delttions)) to M in (n) and ((m) time, respectively. Upon querying 'D with vector IR", it outputs Me in Ö Omm--11j/ + m) time, with high probability, where d' the largest corrupted VC-dimension of M throughout the history of its updates.
The idea of this reduction to split the columns of M into log n matrices M ..., Mog where M, contains at most 2' columns. Each M, is used as input to a static OMv data structure which is reinitialized whenever M, changes which occurs at most once every 2 updates to M. This allows to amortize the reinitialization cost over multiple updates.
Lemma B.7. Assume there is static OMy data structure for matrices of size mxn with preprocessing time Pm,, n.) and query time Qmm, n.). Then there exists a dynamic OMv data structure supporting row and column insertions and deletions. The preprocessing time is ((pmm, n)), the amortized row update time
log
P(2i, .n) Σ j=0
2
for column updates
log n
(mm,
O
20
and query time is Ö(Q(m,)) n)). This reduction runs several static OMv data structures, each receiving a submatrix of the dynamic imput matrix.
We start by proving column updates only, then extend the reduction to support row updates well. Lemma B.8. Assume there is static OMv data structure for mutrices of size X with prepro- cessing time P(m,n) n) and query time Q(n, Then there exists dynamic OMy data structure supporting column insertions and deletions. The preprocessing time is ((P(m, ())), the query time is (QQmm, n)), and the amortized update time is
log m
P(m, 2¹)
2
This reduction runs several static OMv data structures, each receiving a submatrix of the dynamic input matrix.
Proof. Let M be the input matrix that changes over time.
23

---

Initialization. We run log instances of the static OMv data structure, where the ith instance is guaranteed to run on a matrix with at most 2' columns. Let M M be the respective input matrices to these instances. Initially, only the last (i = log n.) data structure receives the initial matrix M as input, and all other instances of the data structure initialize on an empty matrix. Hence initialization takes ((P(m, n)) time.
Insertions. Whenever there is a column insertion to M we reinitialize the ith static OMv data structure that new matrix. When M has more than 2 columns, then all columns removed (i.e., we set M = 0) and inserted to matrix M6+1), All column insertions to M are passed to ( Observe that any M is updated every 2 updates to M, hence the amortized update time is
log n
P(m, 21)22
Queries.
We can answer queries by observing that
M =
M
So, for query vector e we split it into corresponding pieces (0)) (log and query each (()) The time for this is
( n) logn)
because each 6 submatrix of M and we have log such matrices.
Deletions. When deleting column of M, we do not delete the column from the respective M Instead, all future query vectors will have extra 0 entry for the deleted column.
When all columns from ( are appended to M (++1) because of some insertions, then the deleted columns are not appended to M Hence whenever a static OMv data structure initialized, is submatrix of the imput matrix M.
When there have been 2 /2 postponed deletions to any ( then the columns are actually deleted and the respective static OMv data structure is reinitialized on the new ( The remaining columns in ( all exist in the current dynamic input M, so again, the static OMv data structure receives a submatrix of M input. For any one this takes amortized O (P,n, 2 time which is subsumed by the complexity of handling insertions.
Observe that internally, our matrices ( always at most twice their intended size because the yet to be removed columns. Thus the query complexity increases by at most a constant factor.
We now prove Lemma B.7 (Row& & Column Updates)
Proof. Here, we extend Lemma B.8 to support row updates as well. The reduction follows the same idea as L.8
Let be dynamic input matrix. We run log copies of the column update data structure Lemma B.8 on matrices N(O), ..... ".,,,.,,h,, (loggn) with the i'th matrix having most 2' rows. When inserting new rows to N, they are passed (()) When ( has more than 2 rows, all rows appended 1)+1)) When rows appended to any N the respective data structure is reinitialized. To handle deletions, we remove the respective row from the output until 2' /2 rows have
been deleted from N then the rows are removed from O and the respective data structure is reinitialized. The amortized update time thus becomes
log n Time to initialize Lemma B.8 on 2 X n matrix
log m
P(2), n2)
=
Σ 1=0
2i
2
1=0
For column updates, each of the O receives a new column, so each of the log m column update data structures is updated which takes;
log m logn
P(2 2
logn Σ
P(m, 21)
Σ
Σ
=
2'
2
1=0
1=
24

---

because geometric sums are bounded by their largest term in Onotatioo.
Finally, the query time
log m
Σ
Q(22, = Ō(Q(m, n)),
which proves the lemma.
We now prove Theorem T.4 Dynamicc OMv for corrupted VC-dimension d).
Proof. The initialization cost of static OMv is P(m, n) = (mm). and the query complexity is Qmm, n) =
m) by Theorem 1.3 This complexity also holds for submatrices, i.e., Q(a, b) (mmm 1/4 + m) for any a sized submatrix.
Thus we have update time for column updates:
log
P(m, 29)
log n
m2
Σ
0
Ō(m)
2
1=
and for row updates we have
log
P(2), m)
log
2'n
o
Σ
= =Ō
Σ 1=0
Ö(n)
20
23
and for query time we have
Ō(Q(m,n) S Õmmm² 1- + m),
which proves the theorem.
B.4 Extension to Structured Non-Boolean Matrices
In this section, prove result for suhquadratic-time accelerated matrix-vector multiplication for non-Boolean matrices, when the analogous Pollard pseudodimension is bounded. We also list further applications of this result.
Theorem B.9. Suppose that the Pollard psendodimension of the matrix M E Ruxn is d. and that the number of distinct values per column is < T. Then, after an m(Tmm) time preprocessing. there is a data structure that, upon receiving a vector E TR?", returns Mu in time O + m)) Remark B.10. When M is the weight matrix of a neural network and v is the activation output from the previous layer of the neural network, the matrix-vecios product Mu corresponds to running inference on with the neural network M. This is a key step in a number of applications, includ- ing online optimization in unknown no-linear systems [Lin et al. 2023b) and inference in large language models. Dehghankar et al. (2024) studies the latter application with ternary matrices M E 1, 1)nimm and shows that they amenable to O log n) multiplication. If M has bounded Pollard pseudodimension d, then as 3, we obtain a polynomial acceleration on this result: by Theorem B.9 the matrix-vector product can be computed in 0(mm 1-1/d n) time.
Recall the definition of the Pollard pseudodimension:
Definition B.11 (Pollard Pseudodimension). For a family of functions F mapping X to Y, the Pollard pseudodimension F, denoted by Pdim(F), is the VC dimension of the set system (X x Y,, (l(2, v) f(x) Z w} f F}).
In the setting of matrices M E _ interpret each row function fM,; + M M. In
particular, when M has Pollard pseudodimension d, then that means the set system ([r] x IR { {(.
M., y) E [m]}) has VC-dimension d. Restricting the groundset [n] x R to {(- 3i M.j = y) does not increase the VC-dimension. This latter set system can be interpreted as the following Boolean matrix N:
Given matrix M E Taxx where each column has at most distinct values, consider the following construction of an N E {0, 1mxxT matrix. Let Y BT be the distinct values per column of M
25

---

(we may duplicate values if column has < T distinct values). Assume the entries in each column of Y are sorted in increasing order. Let Ni 1 2
For example, the following M has at most T = distinct values per column:
1
-1
1
0
0
0
1
0
0
-2
4
2
0
0
1
M =
2
4
1
1
1
N,
Y
5
3
1
0
1
4
3
0
0
1
Since matrix is Boolean and of VC-dimension at most d, we can run our fast matrix-vector product data structures it (e.g., Theorem
1.3).
Proof of Theorem B.9 Given M E mmmxn we construct the Boolean matrix N E {0, [0.11mxxar x as previously described.
We initialize Theorem
1.3 on N which takes m(Tmm) time. Multiplying vector v' R with N takes O(Tum--1fd + m) time. We are left with explaining how to compute Me via Nu'.
We have
M.j Y1,
E
Ykj Yk-15
k> SM.
-NoT NIiTHH YR-1s)
In particular, compute Mu Ne'where T//T= = Uj Yı,o V'ST+ = uy (Yaj YK-15) for k 2.
Constructing o' takes OTT)) time per query.
Matrices with small constant Pollard pseudodimensions are also prevalent in real-world data, and capture similar notion of structure as matrices with low constant VC-dimensions, For instance, the following are examples of matrices with small Pollard pseudodimension.
Definition B.12 (Multiball vectors). Let u V be vertex of the graph G. Let be a real number and A be set of distances -c 50 < ōn <... de-1 < < co. Define the multiball vectors as follows:
MB r, A) = (yu)evv where yu E [E] is the smallest integer such that u E B(v, r + 6ym)-
Let MBG.A (MB((,r A) V E R} be the set of all multiball vectors in G with shifts A. Theorem B.13 (Karezmarz and Zheng (2024). ) For a Ki--mnorrfrre graph G. for any set of distances, the set of multiball vectors MBg, has pseudodimension at most -
C Applications
In this section, we consider some applications of our OMy result Theorem 1.4 These applications have quadratic ((n2)- lower bounds, conditional on the OMv conjecture. We show that on structured graph this lower bound can be beaten.
C.1 High-accuracy Dynamic Laplacian Solver
Theorem 1.6. (Dynamic Laplacian Solver). There is dynamic algorithm that, given dynamic
graph G = (V, E) with corrupted VC-dimension bounded by d, maintains a Laplacian system solver.
The data structure supports queries that receive a vector E IR RR and error parameter > Then,
in 2-1d log 1/e) time, the algorithm returns the (approximate) solution to Lx = b where
|| x= - <| [||z=||t. ||.. Each vertex update G takes ((r) time.
26

---

We consider the setting where the Laplacian L corresponds to graph with bounded VC-dimension. First, recall the notion of spectral sparsifiers.
Definition C.1 ((1 + speectral sparsifiers). Let Lx denote the Laplacian of any undirected graph X. Then, a (1 + s)-sptcaall sparsifier H of a graph G is subgraph of G such that for every vector R
LHæ (1-c)x L S
xx LGx S (1+ LH
Then, result from Abraham et al. (2016) provides construction for a dynamic spectral sparsifier under edge deletions and insertions with polylogarithmic amortized update time:
Theorem C.2 (Theorem 4.1 of Abbraham al. (016]). There exists fully dynamic randomized
algorithm with polylogarithmic update time for maintaining a (1 = sparsifier H of graph G. with probability least 1 1/n" for any < c < and 2 Specifically, the amortized update time of the algorithm is O(ee-2log) p plog n) and the size of H is O(ene logg plog" n log W ), where S S m is parameter of choice. Here, W is the ratio between the largest and the smallest edge weight G.
We the following result for solving Laplacian systems in the static setting.
Lemma C.3 (Kyng and Sachdeva (2016). There is randomized procedure that given any n-vertex m-edge graph with Laplacian matrix Lg, and vector b E RV such that there exists an a E RRV with L = b computes E E RY with I|z x1|T.G S c||=:||.. in Ö(m log with high probability.
Lemma C.4. Let G be a dynamic graph and let A be its dynamic adjacency matrix. Assume there is dynamic OMv data structure for this A with update time (n) and query time (nn).
Then there exists dynamic Laplacian System solver for the same dynamic graph G, supporting updates to G in (U)(n) + n) time. The data structure supports queries which for any given b E TR and e > 0 in (())n) log 1/c) time return RV with || x= Lo I <e|x*||La where x² is the exact solution for Lg b.
Via Theorem 1.4 we have U(n)= (()) and ((n) = ((n2-1/)) thus obtaining Theorem 1.6
Proof. We two separate data structures. The first is dynamic spectral sparsifier Theorem C which maintains spectral sparsifier zs LG with error 1/2. We also run the dynamic OMv data structure for matrix A (adjacency matrix).
The update time is thus Ö(n + Unn)) as the spectral sparsifier needs polylog time per edge updates, thus (n) time for node updates.
Queries When given a vector b E R and error parameter >> O, we use H as preconditioner for the linear system LGæ = We can multiply with H-1 by running a static Laplacian system solver Lemma C.3 which takes ((n) time per product as H has (nz) edges. In particular, we let
b
and then perform iterative refinement (Richardson iteration)
x [+1 + x' - -H HHH(LLL'' - b).
After Ö(lg 1/e) iterations we have I| x Ille |||x=||LO.
Each iteration takes Ö(n Q(n)) time, where Ö(n) the time for multiplying by H and ((n) the time for multiplying by LG. Observe that LGu = Dv - Av where D is a diagonal matrix and A an adjacency matrix. So the first product takes (n) time and the second product is handled by the dynamic OMv data structure in ((((n)) time. Together, this proves the lemma.
C.2 Effective Resistance
The following Theorem 1.7 is corollary of the dynamic Laplacian solver from Theorem 1.6
27

---

Theorem 1.7. (Dynamic Effective Resistance). There is dynamic algorithm that, given a dynamic graph = (V, with corrupted VC-dimension bounded by d. maintains effective resistances in G. The data structure supports queries that receive a pair of vertices u, V and error parameter <> O. Then, in O(n211/d 2-d log 1/c) time, the algorithm returns (1 =c) appproxiimatoon of the effective resistance. Moreover, each node update to G in the dynamic data structure takes O(n) time.
Proof. The effective resistance of a pair v E V the energy of an electric flow, routing one unit of flow between and v. The energy of an electric flow f E R is Ee Se and the electric flow is given by f BL (e,, e,)) where B (, 1) ExV is the incidence matrix of G with arbitrary directions. Thus the effective resistance is
BBL BL (c.
e. e.) (ea c.) L BL (eu cv)
[Ca - -e,) L (ev ex).
This can be computed via the dynamic Laplacian system solver in Theorem 1.6
C.3 Triangle Detection
Theorem 1.8. (Dynamic Triangle Detection). There is algorithm that, given a dynamic graph G = (V, E) with corrupled VC-dimension d, maintains whether G has triangle or not. Each vertex update takes ( time and returns Boolean indicator for G containing triangle.
The result follows form the following lemma for (nn) = Ö(n) and ((n) = Ō(n2-1/d from Theorem L.4
Lemma C.5. Let G be dynamic graph and let A be its dynamic adjacency matrix. Assume there dynamic OMv data structure for this A with update time U (n) and query time Q(n).
Then there exists dynamic triangle detection algorithm for the same dynamic graph G, supporting updates in (U (n) + Qn1) time.
Proof. Let be adjaceney matrix of the graph, then the diagonal entries (A and only if u participates in a triangle. Thus by maintaining the sum (A.) 9)2 we can detect if there is any triangle in the graph.
3 "),y v are non-zero
We maintain the sum follows: updated.
Let A be the incidence matrix before, and A after node is
Then
E(A (A9)))+ (A (A²)e..
difference in # of triangles participates in
This is because each triangle participates in is counted thrice in the (once for each vertex of the triangle). Thus we can maintain the sum by computing (A²)), )e,e and (A 3) (.... Observe that this is the cictor-marrx--veetu product of (i) the wth row of A, (ii) matrix A, (iii) and v-th column vector of A. Thus can be computed in (Q((n) time, with an extra (n) time to update to A'.
C.4 Single-Source Shortest Paths and k-Center
Lemma C.6 (Brand et al. (2022). Assume there is a dynamic distance oracle for unweighted undirected graphs with the following operations.
An initialization procedure that given (V, E)
and a threshold 1 < d S n.
A node update operation with update time Unn, d).
A query operation which for any source node, given during the query, returns the d-bounded single source distances (QQ(n, d)). That is, return for each E the distance if it is at most d, or oo if the distance is d.
28

---

Proof. We first describe how to obtain a dynamic distance oracle that yields distances to 1/e. This is done by running the dynamic OMv data structure of Theorem I.4 on the adjacency matrix of G. Then single source distances up to 1/e from source vertex u can be computed by repeatedly The smallest Then for any 1 1 k S Tt and e > O there exists dynamic (1 + c) -approximate single source distance data structure on unweighted undirected graphs. It supports node updates in
o O
nh 4
k
n
Q
n.
+
k
time.
Theorem 1.9. (Dynamic Approximate Single- Shortest Paths). There is a dynamic algo- rithm that maintains (1 + -upproxximatte single-source distances on dynamic unweighted graph G E). If the corrupted VC-dimension of G is bounded by d, each node update to takes O(kn /c) time, and querying the distances for any source node takes 2 (e) time.
multiplying + Aw for initial Cus i.e., we compute A Ev, for 2...... 1/c. with (A' (e ) # 0 is the smallest number of steps to reach from to v, i.e., the distance between the vertices.
This data structure internally constructs the a A-labeled spanning tree of the boolean matrix A, where the weight of the tree gives us the time complexity per query. Hence, while do not know the corrupted VC-dimension d, we do know how much time each query is going to take.
So when running Lemma (.6maaC.6Jon the above distance data structure, we can pick k: = nT where T 2 n is the weight of the spanning tree. Thus, we get the update time
k -T nk + 6
n² k
nVT
δ
n1
+
VT
Ö(n 2-
2 )),
which proves the claim.
Theorem 1.10. (Dynamic Approximate k-center). Given an unweighted undirected graph G= (V,E), E), there is dynamic algorithm for (2 + -a-pprooxea k-center with node update time O(kn2-1/2d where d is a bound on the corrupted VC-dimension of G.
This result is a corollary of Theorem 1.9 as k-center can be reduced to computing k-single source distances.
Given graph G (V, a positive parameter S 1/2, and dilll---ymmicc data structure that maintains (1 + aaprooxittt single source distances with update time T'n, m, e) and Q m, query time, there a dynamic algorithm that maintains a 2(1 + 4e) app-roipoxe solution to fully-dyaamie k-center in time O (n, m, E) (Q(n, m, c) n)).
Lemma C.7 (Theorem 7.3 by Cruciani al. 2024|
D Characterization of matrices with constant VC-dimension
In this section, we provide a characterization matrices with constant VC-dimension. Particularly, prove Theorem I.1 and state a number of examples of other constant VC-dimension matrices.
Fact 1. Consider a hereditary class of 0/ 0/1-matrices M, meaning that M is closed under row/colunn deletion (i.e., each matrix M E M is still in M after deleting a row or column). M is non-trivial, (i.e., does not contain every possible matrix), then there exists absolute constant e E such that the VC-dimension of any matrix in M is at most c.
Fact 1.1 provides a structural characterization of some matrices with constant VC-dimension,, and it an analogous result to the fact that non-trivial hereditary classes of graphs have low VC-dimension. To prove Fact [.I introduce the notion of a bipartisation of graph.
29

---

Definition D.1. A bipartite graph H (AUB, is a bipartisation of graph G if removing all edges in A and B in G yields H for some partition A, B of (()). A graph class G said to be hereditary if it is closed under induced subgraphs.
Lemma D.2 (Lemma 3.4 of Bousquet et al. (2015). ). For any hereditary class C of graphs and for any bipartite graph H, if the graphs C have infinite VC-dimension, then C contains graph G whose bipartisation is H.
By transposition, we get the following corollary:
Corollary D.3. The equivalent contrapositive statement that for any hereditary class of graphs and for any bipartite graph H, ifC does not contain a graph G whose bipartisation is H (AUB, F) where U V(G), then the graphs in have finite VC-dimension.
Lemma D.4. The VC-dimension of any matrix in M is upper bounded by a finite constant.
Proof. Since M M is Boolean, can treat it bipartite graph G, with rows representing left vertices and columns representing right vertices. In particular, we can treat M as class of bipartite graphs closed under vertex deletion (row deletion = deleting left vertex, column delction deleting a right vertex). Thus we can apply Lemma D.2 M..
Since M is non-trivial, there must be some graph H not contained in it. For this excluded graph H, define H' as the same graph but add one extra left vertex and one extra right vertex. Connect this new left vertex to every vertex the right, and connect the new right vertex to every vertex the left. Note that since H was not contained in M and it is closed under vertex deletion, H' also cannot be contained in M.
Now assume there is E MM that contains H' as bipartization. Then there is a partition A, B of V. such that keeping only the edges between A and B of G. results in H'. Because of the left vertex in H' that connects to all right vertices, and the right vertex connecting to all left vertices, we must have that A are all left and B are all the right vertices of G (or the other way around). But that means no edges were removed from G when restricting to edges between A and B, since a bipartite graph by definition only has edges connecting left and right vertices. So G H' and H' E .M. This is contradiction because by construction of H', it does not exist in M.
We conclude, that set of bipartite graphs corresponding to M does not contain any graph whose bipartisation H' Hence by Corollary D.3 the VC-dimension must be a finite constant. Note that this is equivalent to the VC-dimension of the adjacency matrices being bounded, but M are not adjacency matrices. The adjacency matrices are of form
0
M
M
0
for matrices M E M. We already argued that each adjacency matrix has constant VC-dimension, and since removing rows does not increase the VC-dimension (it is equivalent to deleting sets), this implies M also has constant VC-dimension. In conclusion, each matrix in M has constant VC-dimension.
D.1 Examples of low VC-dimension matrices
We provide some broad families of matrices with constant VC dimension.
Adjacency matrices of H-minor free graphs. Eppstein 1995 showed that H-minor free directed graphs (where the minor can be obtained through vertex deletion, edge deletion, and edge contraction) has VC-dimension at most [H 1. As immediate consequence, since bipartite-graphs triangle (K₂) free, the VC-dimension of any bipartite graph is 2. As a consequence, given any adjacency matrix A of fi-mioor free graph G, for any & > 1, A is the adjacency matrix of H!- minor free graph G' (since A corresponds to the reachability graph where an edge (u. v) E E(G') corresponds to the existence of a kellngth walk between u and v in G). Therefore, the VC-dimension of A K is also at most [V(H) - 1.
Adjacency matrices of interval graphs. Interval graphs are the intersection graphs of a family of intervals on the real line. Then, since the hypothesis class of intervals on the real line H = (1a, < < b} has VC-dimension 2 (any two points can be shattered by choosing an interval that
30

---

includes one or both points, but no set of three points can always be shattered), every interval graph has VC-dimension at most 2.
Boolean kernel matrices. A matrix where each column i (and each row) receives some label & E I. from some (possibly infinite) set of possible labels T., Then, suppose each entry of M satisfies M.j- f(e,, Lÿ) for some function f f L + {0, 1.. For example, the labels could be points in L Rd with f being indicator that the distance is at most some threshold. If f, L is fixed (i.e., independent of the number of rows/columns) then these graphs are closed under row/column deletion and thus have bounded VC-dimension by Theorem T.1
Shortest-patee structures. Let G be undirected graph with non-negative edge weights and let S be a subset of its shortest paths such that, for every pair (u, v) of distinct vertices, S contains exactly one shortest path between u and Marie de Lima al. 2023 defines range space associated with S and proves that its VC dimension is 2.
A Adjacency matrices of planar graphs. Let G be planar graph. Then, there is planar drawing of G, and deleting vertices and edges retains this property. Therefore, these graphs are closed under row/column deletion and thus have bounded VC-dimension by Theorem 1.1
Adjacency matrices of semi-algebraic graphs of bounded description complexity. By the Milnor- Thom theorem in real algebraic geometry [Matoušek] [2002] and Assouad's ' theorem [Assouad] 1983). semi-algebraic graphs of bounded description complexity have constant VC-dimensions. In turn, this extends to adjacency matrices of string graphs where every two curves intersect.
Practical matrices. Coudert et al. 2024 computes the VC-dimension of families of graphs that arise in practice, from protein interaction networks to autonomous Internet systems. Even for such graphs with millions of nodes, the VC-dimension of the graphs are typically between and 8.
E Numerical Simulations
The algorithm from Theorem 1.3 has previously been described in Björklund and Lingas) [001] and Alves et al. [2024). The latter already experimentally verified the efficiency of the algorithm on real- world data sets and observed that it beats the naive quadratic time matrix vector multiplication. 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 efficient in practice, we here complement the result with a few experiments" As we give theoretic bounds parameterized by d, our experiments focus on the d-dependence too.
Matrix Generation. Since we want to study the complexity dependence on d, we fix the matrix dimension to = 22 4096 and run experiments for d = 2, .... 12. The maximum d is 12 because so we do not need to consider
the VC-dimension S log(n) was picked due to execution time constraints. The n X Binary matrices are generated by sampling ii.d uniform (6) E [0, 1]", 6(%) E [0, d/2) for i = 1,..., n and ( E [o. 1]dd for j 1,.... n, and letting M. = 20) The range for the (()) was chosen so that neither M nor 1 - M sparse, which otherwise would allow for naive matrix multiplication to already beat O(n?) time. The set system of linear classifiers has VC-dimension d. so the corrupted VC-dimension M is upper bounded by d. This implies that the respective MST has weight at most (-ndd//d), Figure ] 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.
log(n). The matrix size n
Complexity. For the matrix vector products generate i.i.d. uniform vectors [0, 1]" For each d, we compute 1000 matrix vector products and measure the run time. Figure Iisows the mean and standard deviation of the observed time. We also compare the time the naive numpy matrix vector multiplication. Figure 2 shows that, since matrix size n is fixed, the time complexity of numpy is constant for different d, whereas the MST-based algorithm is substantially faster for small d. As d increases, the gap gets smaller as one would expect, given the Ö(n 2-14/ theoretic upper bound. The experiments were conducted on an Apple M4 Pro macOS model with 12 physical cores / threads, and 48 GB unified memory RAM, and an Apple Accelerate Framework BLAS backend. The total
'The code for the experiments is available at https:///gthhbb.cc/mmmmeleeeeeee wtt_ooo__aa______eeee ctt_x__eetttr______ee vector_multiplicatiio
complexity
31

---

-109
4
MST column weight
3
2
1
0
2
6
10
12
Ambient Dimension of Set Systenm
Figure I: Weight of the A-labeled spanning tree for 2 2 matrices generated from halfspaces in dimensions.
0.8
H8
10
0
0.6
Runtime (ms)
0.4
0.2
4
6
10
12
Ambient Dimension of Set System
Figure 2: Average run time of the MST-based matrix vector algorithm (bold) and naive numpy matrix vector multiplication (blank), with I-sigma error bars. Horizontal axis is the dimension of the points and halfspaces used to construct the matrix.
amount of time to run the experiments was 30 minutes. No GPU acceleration was used; all matrix operations ran on CPU.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide theoretical proofs for each claim made in the abstract and intro- duction. We do not make any other simplifying assumptions, and we explicitly discuss the limitations of this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We explicitly discuss the limitations of results in the paper: the lack of matching lower bounds to verify if the scaling with the VC-dimension is optimal, and the sub-optimality of the non-Boolean setting.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
33

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
We provide clear and formal mathematical proofs to support each claim.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We provide a full description of the algorithms and experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
34

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our simulations synthetic matrices. We do provide open source code with sufficient instructions to reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
publitc/guudee//odeSattmt httpsi//aanaaeeeeedeeetiiasssaaa www.aaabiiiiiooooooooooooooooiie
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips /nipsscc/pput
guides/ PoodeSSumissiinooo......ooo
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The test details such as matrix size and dimension and how they were chosen have been described in both appendix and in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
The observed time complexities are accompanied by I-sigma error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our numerical simulations section in the Appendix lists the hardware specifi- cations used, and the total time to run the experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't fidn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics (tctpp/s//eeuiiss..ccppubbb////e ces
Answer: [Yes]
Justification: The research conducted in this work conforms, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This work is theoretical and foundational nature, As such, is not tied to any specific applications deployments.
Guidelines:
36

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
37

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.paperssit
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any crowd-sourcing nor any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (TRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve any crowd-sourcing nor any research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
38

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatt:p//eearrpppcc//ooofeeeeeee/ /ct/////oeeeeeecc///2////1. for what should or should not be described.
39


Reviews:
[{"review_id": "uDF9JyBjb0", "reviewer": "Reviewer_9Lbq", "summary": "The paper considered the problem of preprocessing a $m\\times n$ 0/1 matrix $M$, such that matrix vector queries on $M$ can be efficiently implemented. The main takeaway from this work is that if the VC-dimension of the rows of $M$ is at most $d$ then matrix vector queries can be implemented in time complexity $mn^{1-1/d}$. They have also considered both static and dynamic online variants of this problem. The paper as applications of the above result give efficient algorithms for the following problems \n\n1. Dynamic Laplacian solver\n\n2. Dynamic effective resistance of graphs\n\n3. Dynamic triangle detection\n\n4. Dynamic approximate single-source shortest paths\n\nThe authors fundamentally use ideas from computational geometry. Specifically, they use trees of low crossing number for set systems with low VC dimension, a fundamental result in both computational and combinatorial geometry.", "questions": "None", "limitations": "None", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper is well written and well motivated. \n\n2. The overall presentation is good. \n\n3. It introduces ideas from computational geometry to address a matrix problem in a novel way. \n\n4. It gives multiple important applications of their central result.\n\nThere are no obvious weaknesses in this paper.", "was_revised": true, "final_justification": "I am in favor of accepting this paper, as it makes a fundamental contribution to an important problem that is highly relevant to machine learning.", "rebuttal": "We thank the reviewer for their kind review. \n\nPlease don’t hesitate to follow up if any questions come up.\n\nThanks,\n\nAuthors"}, {"review_id": "Jf6QCHun4w", "reviewer": "Reviewer_TRxg", "summary": "The paper provides a theoretical explanation on the speed up observed in some recent practical algorithms for matrix-vector multiplication through preprocessing of matrices. In summary, the paper proves that for  an n × n matrix M of VC-dimension d, the matrix-vector product Mv can be computed in O(n^(2−1/d)) time for any vector v, after preprocessing in O(n^2) time. This is in contrast to the theoretical bounds showing that matrix-vector multiplication over sufficiently large fields require \\Omega(n^2/ log n) time, where the authors claim that the speed up in practice comes thanks to the structure present, measured through the low VC dimension.", "questions": "- The authors argue that most real data has “low constant VC-dimensions”. Can you please better qualify this claim? Can you provide examples? A better example would be to show (in practice) an increase in the speed up with a decrease in the VC dimension of the data. \n\nMinor issues: \n\n- Line 248: semiring -> semi-ring\n\n- Line 258: Can you better explain what you mean by “ algorithms with predictions regime” ? \n\n- Line 261: “ Our dynamic algorithms” -> which algorithms does this refer to?", "limitations": "Yes. The work is purely theoretical.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Overall, this is an interesting theoretical paper that explains an important practical phenomenon. The paper is well written. It motivates the problem well with a very comprehensive background on the literature. This is far from my field of study, so I was not able to follow the proofs, but I was able to appreciate the solution steps and the logic behind the arguments. \n\nOn the other hand, the main weakness of the paper, in my opinion, is whether it is a good match for NeurIPS. I would have expected this result to appear in a more theoretically inclined venue. \n\nFrom a more technical point of view: the solution mainly provides a (partial)  theoretical explanation of the speed up observed in practice, but does not provide any insights or guidance to come up with more efficient algorithms based on the VC dimension of data.", "was_revised": true, "final_justification": "Thank you for your responses. I leave the decision of whether this is a good fit for the conference or not to the Area Chair. Based on all the reviews and the responses, I have increased my score to 4.", "rebuttal": "We thank the reviewer for the kind review. Please find our response below.\n\n> Choice of venue\n\nThe submission is indeed of a theoretical nature, and the NeurIPS call for papers explicitly lists theory as an area of interest. Given the central role of matrix-vector products in learning algorithms, and the prevalence of structured inputs in learning tasks, together with the fact that one of the analyzed algorithms was used to speed up learning in Graph Neural Networks [2], we believe that our results are a good fit for NeurIPS.\n\n> Technical point of view & Guidance/insights for algorithm design\n\nIn addition to explaining the speed up of previous algorithms, we did also provide a new algorithm for when the matrix transpose has low VC-dimension (this is important since the previous algorithm is only efficient for the case where the matrix has low VC-dimension, but the transpose of a matrix can have a VC-dimension that is exponentially higher), as well as data structures for the dynamic setting (where the matrix is allowed to change over time).\n\nRegarding algorithm design, our results and new algorithms form a tool for constructing efficient VC-sensitive algorithms. Using our dynamic matrix-vector product algorithms, we provide several new algorithms for various dynamic graph problems in the applications section (e.g. dynamic effective-resistance and all-pairs-shortest-paths computation). For these problems, there are known $\\Omega(n^2)$ lower bounds that hold for general graphs, but with our new VC-sensitive algorithms one can now construct faster $O(n^{2-1/d})$ upper bounds when the input is structured (i.e., has low VC-dimension). \n\nNotably, our data structures do not need to know the exact structure of the matrix/graph (e.g., the algorithms are not restricted to a specific structure like geometric intersection graphs), and they also do not need to know/compute the VC-dimension. Hence, our data structures are widely applicable as subroutines to other problems. \n\nMoreover, since computing the VC-dimension is $\\Sigma_3^{\\mathrm{P}}$-hard, no efficient algorithm should compute the VC-dimension. So if the dimension is needed by an algorithm, it would restrict applications to cases where the specific structure, and thus VC-dimension, is known.\n\n> Low constant VC-dimension in real data \n\nWe thank the reviewer for this question. We would direct them to [1] which computes the VC-dimension for several real-world datasets (e.g. web graph, protein interaction networks, etc.) and shows they are low constants (i.e. between 3-8). Moreover, the matrix-vector product algorithm has been experimentally observed to be fast in practice in [2], but they haven’t studied the observed running time with respect to different VC-dimensions. We can add an experiment that “smoothly” parameterizes with d, and add a figure as well as an open-source code link for the implementation in the main body. \n\n> Question on algorithms with predictions regime\n\n“Algorithms with predictions” refers to algorithms where one has some prediction of the future/online input ahead of time. This model is studied in many different contexts (online algorithms, streaming, data structures, etc [5]). For matrix-vector product data structures, the assumption is that knowledge about the future vectors is known during preprocessing already, allowing to precompute information for future queries [3,4].\n\n\n> Question on “Our dynamic algorithms”\n\nThanks for requesting more clarity on this. The algorithms we refer to are _all_ the dynamic algorithms in the paper, i.e. Theorems 1.6-1.10 (dynamic Laplacian solver, effective resistances, triangle detection, single-source shortest paths, $k$-center clustering), and theorem 1.4 which provides our dynamic algorithm for fast Mv.  To be clear, when we say “structured graph” in line 261, we mean a graph with constant VC-dimension. We will add clarifications for this in the paper.\n\nWe thank the reviewer again for their valuable feedback. We hope our reply addresses any concerns in our work, and we would be happy to answer any further questions.\n\n\nThanks,\n\nAuthors\n\n==============================\n\nReferences:\n\n1) Practical Computation of Graph VC-Dimension. Coudert et. al. 2024. SEA 2024\n2) Accelerating Graph Neural Networks with a Novel Matrix Compression Format. Alves et. al. arXiV 2024.\n3) On Dynamic Graph Algorithms with Predictions. Van den Brand et. al. SODA 2024\n4) On the complexity of algorithms with predictions for dynamic graph problems. Henzinger et. al. ITCS 2024\n5) Algorithms with Predictions. Alexander Lindermayr and Nicole Megow. Survey webpage."}, {"review_id": "s7lwVSZ0E8", "reviewer": "Reviewer_rvWp", "summary": "This paper studies the problem of preprocessing a Boolean $m \\times n$ matrix $M$ to support fast matrix-vector product (MVP). The main result of this paper is that MVP can be supported in time $mn^{1 - 1/d}$ with $m n$ preprocessing time, where $d$ is the VC dimension of $M$.\nAs a bonus, this result extends to matrices that are \"close\" to the set $\\mathcal N_d$ of matrices with VC dimension $\\leq d$. Namely, $\\min_{N \\in \\mathcal N_d} \\max_i||M_i - N_i||_\\infty \\leq n^{1 - 1/d}$ suffice (denote with $A_i$ the $i$-th column of $A$).\n\nSince MVP is a fundamental problem, the complexity bound above propagates to several other problems.", "questions": "You claim that your work bridges the gap between MVP heuristics used in practice and theoretical lower bounds. It would be interesting if you could further elaborate on why real-world MVP involve low-VC-dimensional matrices. Could you provide examples of successful heurstics which behavior is exampled by low VC dimension?\nAt line 83 you claim that \"real-world data has low VC dimension\": please elaborate more.\n\nAs written above, this work's results could be compressed into an extremely short note, and I believe that the community would benefit the most if this work was published (perhaps on Arxiv) as a coincise note.", "limitations": "Yes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This work is, to the best of my knowledge, the first to parameterize the complexity of MVP with respect to the VC dimension of a the matrix. The techniques employed to design the data structure achieving the desired time bound are the following.\n\nFirst, the authors define a spanning tree for a matrix $M$ as a spanning tree of the weighted complete graph over $[n] \\times [n]$, where $w(i, j) = ||M_i - M_j||_1$. Then, they prove a structural lemma showing that any matrix $M$ with VC dimension $d$ admits a spanning tree of weight at most $m n^{1-1/d}$. Finally, they observe that a spanning tree $T$ for $M$ can be leveraged to compute MVPs with $M$ in time $w(T)$.\nTo turn these observations into an algorithm, they use a known algorithm from Indyk and Motwani that computes a $O(\\log n)$-approximate minimum spanning tree over hamming metric in  $\\tilde O(mn)$ time.\n\nThis paper introduces a novel parameterization for the MVP problem and derives novel bounds. I believe that the main result of this work is interesting and certainly worth observing. Nonetheless, I recommend rejection due to the lack of technical novelty. \n\nThe technical novelty of this work is minimal. This work's contribution is a series of simple observation that I believe could be expressed in a four-page note, without compromising clarity.\nLet me briefly evaluate the novelty (or lack thereof) of each of this work's main propositions.\n\nTheorem 1.1 follows from the simple observation that each $n \\times n$ matrix is the sub-matrix of any matrix with VC dimension at least $n$.\n\nLemma 3.4 can be proven through simple algebraic manipulations of the definition of MVP.\n\nLemma 3.12, which proves the main structural result of this work, follows by applying Lemma 4.1 of Welzl [1988] greedily.\n\nLemma 3.13 follows from the classic metric TSP analysis because crossing numbers are a metric.\n\nFinally, and perhaps less importantly, the quality of writing is low. This paper could be much shorter, and thus more readable, if the authors did not add a long list containing several of the obvious consequences of a faster MVP algorithm. Moreover, the density of typos made it hard to understand at first sight. A list of writing mistakes and typos follows.\n\nMISTAKES and TYPOS:\nIn the abstract, you do not say that your result holds for the class of Boolean matrices.\n\nLine 78, \"rows in S\" is unclear. I guess you mean the sub-matrix which columns are restricted to those in S.\n\nLine 79 - 84, you define VC dimension for matrices and then talk about hypothesis classes. A reader who's not familiare with learning theory would get lost here.\n\nLine 90 - 91. I do not understand what you mean here. \n\nDefinition 1.2. I imagine that we're taking the minimum over such d.\n\nLine 150 - 155. What is the threshold of a matrix?\n\nLine 258. Regime -> paradigm.\n\nDefinition 3.8. I imagine the definition that you wanted to give is that A crosses r if $A \\cap r, A \\Delta r \\neq \\emptyset$\n\nLine 368. \\max -> \\Sigma", "was_revised": true, "final_justification": "I revise my evaluation and recommend acceptance, as long as there is room.", "rebuttal": "We thank the reviewer for their detailed comments. Firstly, we thank the reviewer for the careful reading and list of typos, and we will make sure to address these. In the answer below, we start by addressing comments on technical contributions. Then, we address items from the typo list that are not just small edits, or where we believe further context may be helpful. \n\n> Regarding technical contributions & 4 page note\n\nThe reviewer’s comments refer to the proofs in section 3, which prove only the existence of low-weight trees. That part is indeed <4 pages long and (except for the Welzl citation) provides a self-contained proof. We felt that the narrative would be incomplete without formally proving these lemmas in Section 3, since we want to formally argue why the algorithm is efficient.\n\nWe do provide many further technical contributions, such as an efficient algorithm for transposed matrices (which could have exponentially larger VC-dimension) as well as data structures for the dynamic case (where the matrix can change). The respective proofs are contained in the Appendix.\n\n> Theorem 1.1 follows from the simple observation that each nxn matrix is the sub-matrix of any matrix with VC dimension at least n.\n\nThere seems to be a misunderstanding of what theorem 1.1 says. We have shown that for any non-trivial matrix family that is closed under row/column-deletion, all matrices in this family have a VC-dimension that is _at most_ a constant. \n \n- As a concrete example for such a matrix family, consider geometric matrices where rows and columns are assigned points in d-dimensional space and the 0/1 entries reflect distance < 1. For any such matrix, if we delete a row or column, then it is still such a geometric matrix. So this family is closed under deletion and thus every such matrix has constant VC-dimension (which is already known for this specific example). \n\nThe point of Thm 1.1 is that we do not need to know what the structure is, e.g., it doesn’t have to be something that is defined via labels on rows/columns. We don’t need to know what exactly the specific structure/family is: as long as the family is closed under deletions, all matrices of that family have VC-dimension < some constant (i.e. independent of matrix size). \n\n- Our proof for this statement exploits several deep results from structural graph theory, so we respectfully disagree that it's a “simple observation”: If the reviewer thinks there is a simpler way to formally prove the theorem, we would definitely appreciate a clarification: at the moment, we don’t see any connection between Theorem 1.1 and the proposed simple observation.\n\n“Every $n\\times n$ matrix A being a submatrix of a larger matrix B of VC-dimension at least n,” has no relation to Theorem 1.1 because (1) the larger matrix B is generally not part of the family, and (2) a _lower bound_ on B’s VC-dimension does not give a _constant upper bound_ on the VC-dimension of the submatrix A.\n\n> Results for Boolean matrices\n\nWe will explicitly add “Boolean” to the abstract (it’s currently only implicit in the abstract since the VC-dimension is only defined for Boolean matrices). However, our results do extend to real/integer matrices (see Lines 150-155 and Appendix B.4) through our analysis with the Pollard pseudodimension.\n\n> Line 90-91: I do not understand what you mean here\n\nTheorem 1.1 specifies a sufficient but not necessary condition for constant VC-dimension. Lines 90-91 mean to say that matrices can have a constant VC-dimension without satisfying the condition of Thm 1.1 (i.e., there are also other conditions that imply constant VC-dimension. For instance, adjacency matrices of minor-free graphs have constant VC-dimension.) \n\n> Definition 1.2\n\nThe corrupted VC-dimension of a matrix is the minimum such d. That being said, since we provide upper bounds on the time complexity, the parameter $d$ in our Theorems can be any upper bound on the corrupted VC-dimension. It just results in looser bounds.\n\n>Line 150 - 155. What is the threshold of a matrix\n\nThe thresholds are part of the definition of Pollard Pseudodimension (an extension of VC-dimension to the non-Boolean setting). Line 153 should have referenced Appendix A where Pseudodimension is defined.\n\nWhen applied to real-valued matrix $\\mathbf{M}$, the definition of Pseudodimension uses thresholds $T\\in \\mathbb{R}$ to construct Boolean matrices given by $\\mathbf{M}_{i,j} \\le T$. One never needs to consider more distinct thresholds than the number of distinct entries in M. \n\n> Definition 3.8. I imagine the definition that you wanted to give is that A crosses r if $A\\cap r, A \\Delta r \\neq \\emptyset$ \n\nThank you for catching this. Yes, the first formulation of the definition was wrong. The 2nd part (“$A$ crosses $r$ if neither $A \\subseteq r$ nor $A\\cap r=\\emptyset$ holds”) is the correct definition, and that’s also the one we used in our proofs.\n\nThe remaining listed typos will of course also be fixed. We thank the reviewer again for their valuable feedback. We hope our reply addresses any concerns in our work, and we would be happy to answer any further questions.\n\nThanks,\n\nAuthors"}, {"review_id": "4ZGFtw8Mwx", "reviewer": "Reviewer_goCC", "summary": "This paper shows that for n x n Boolean matrices with VC dimension d (where the function class is defined by considering each row of the matrix as the evaluation table of a function), there is an O(n^{2-1/d}) time-per-query algorithm for online matrix-vector multiplication with preprocessing. It also presents various applications and extensions of this result.", "questions": "See weaknesses.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths.** The result gives a novel perspective on beyond-worst-case online matrix vector multiplication: VC dimension bounds are a plausibly natural assumption for real data, and this paper shows that they enable avoiding worst-case quadratic lower bounds. The basic result is an almost direct corollary of combining a (quite practical) algorithm due to (Bjorklund and Lingas, 2001) with an old (and to me unknown) lemma from the computational geometry literature showing that for any function class with bounded VC dimension, there are two points on which \"most\" of the functions agree (Welzl, 1988). Nevertheless making the connection between these two branches of literature is  a contribution in its own right, and the authors put substantial technical effort into extensions and applications of the basic result.\n\n**Weaknesses.** I think there is a (fairly minor) gap in the current proof of the basic result: Welzl's Lemma 4.1 hides some \"constants\" that, I think, actually depend on the VC dimension bound d. The statement of Lemma 4.1 says \"c is a constant depending on (X,R)\", which is completely vacuous since (X,R) is the entire problem instance. From inspecting the proof, my impression is that c ~ O(d) suffices, but this should be checked and perhaps a self-contained modern proof can be included in the paper for completeness. At any rate, a factor of d is not really important since the result already requires d << log n for it to be non-trivial.\n\nAlso, I think Definitions 3.8 and 3.10 are wrong: in 3.8, the symmetric difference between two sets is non-empty iff the sets are non-equal. The second formulation of the definition of crossing is I think the correct one, but it's not the same as the first formulation. In 3.10, I think the crossing number should be \"sum over edges of max over ranges of indicator that the range crosses the edge\", not \"max over ranges of sum over edges\". I believe the correct version is used for the proofs though, so this seems to just be a typo.\n\nI will increase my score if the authors can confirm that these are not serious issues.", "was_revised": true, "final_justification": "The authors' response addressed the minor issues that I found in the proofs. The result is an interesting theoretical contribution (if perhaps a bit niche) and I am happy to recommend acceptance.", "rebuttal": "We thank the reviewer for their detailed comments, and for their constructive feedback to strengthen the quality of our paper. Please find our response below:\n\n> I think there is a (fairly minor) gap in the current proof of the basic result: Welzl's Lemma 4.1 hides some \"constants\" that, I think, actually depend on the VC dimension bound d. The statement of Lemma 4.1 says \"c is a constant depending on (X,R)\", which is completely vacuous since (X,R) is the entire problem instance. From inspecting the proof, my impression is that c ~ O(d) suffices, but this should be checked and perhaps a self-contained modern proof can be included in the paper for completeness. At any rate, a factor of d is not really important since the result already requires d << log n for it to be non-trivial.\n\nThanks for raising this point. After checking Welzl’s proof of Lemma 4.1, we see that $c = O(d)$ indeed does suffice [1]. The proof of Lemma 4.1 in [1] should use $c_0 = O(d)$ because of the $8d$ factor in Proposition 2.4 of [1]. Parameter $c_1$ is chosen as $O(c_0/c)$ and needs to be $O(1)$ for the proof to go through. So it suffices to pick any $c$ bounded by $O(d)$.)\nWe will add the respective updated proof to the appendix.\n\nThis adds a $d$ factor to our time complexities, which (as the reviewer correctly points out) is at most a log-factor because $m\\times n$ matrices can have VC-dimension at most $\\log(m)$. However, since our $\\tilde{O}$-notation hides such log-factors, this does not affect our algorithms and proofs. Therefore, our main result is unchanged.\n \n> Also, I think Definitions 3.8 and 3.10 are wrong: in 3.8, the symmetric difference between two sets is non-empty iff the sets are non-equal. The second formulation of the definition of crossing is I think the correct one, but it's not the same as the first formulation.\n\nThank you for catching this error. Yes, crossing has nothing to do with symmetric difference, and we will remove that first formulation. However, as the reviewer correctly points out, we did in fact only use the second formulation of the definition of crossing ($A$ crosses $r$ if neither $A \\subseteq r$ nor $A\\cap r=\\emptyset$ holds) in the proof of Theorem 3.7, so this does also not affect the main result. \n\n> In 3.10, I think the crossing number should be \"sum over edges of max over ranges of indicator that the range crosses the edge\", not \"max over ranges of sum over edges\". I believe the correct version is used for the proofs though, so this seems to just be a typo.\n\nYes, that’s a typo. Thanks for pointing this out, and we will fix this typo.\n\nWe thank the reviewer again for their valuable feedback. We hope our reply addresses any concerns in our work, and we would be happy to answer any further questions.\n\nThanks,\n\nAuthors\n\n===========\n\nReferences  \n[1] E. Welzl. Partition trees for triangle counting and other range searching problems"}]

Author rebuttal:

Meta-review: Reviewers' scores are all positive (after rebuttal). The authors' response successfully addressed questions about some technical details. While some questioned the paper's fit for NeurIPS, given the wide use of matrix–vector multiplication in ML algorithms, I believe that this work fits NeurIPS well. One reviewer felt the technical contribution was somewhat insufficient, but the overall sentiment is that the technical contribution of this paper is above the NeurIPS acceptance bar.
Decision: Accept (poster)