Online matrix-vector multiplication problem

Unsolved problem in computer science

Is there an algorithm for solving the OMv problem in time ${\displaystyle O(n^{3-\varepsilon })}$, for some constant ${\displaystyle \varepsilon >0}$?

More unsolved problems in computer science

In computational complexity theory, the online matrix-vector multiplication problem (OMv) asks an online algorithm to return, at each round, the product of an ${\displaystyle n\times n}$ matrix and a newly-arrived ${\displaystyle n}$-dimensional vector. OMv is conjectured to require roughly cubic time. This conjectured hardness implies lower bounds on the time needed to solve various dynamic problems and is of particular interest in fine-grained complexity.

Definition

In OMv, an algorithm is given an integer ${\displaystyle n}$  and an ${\displaystyle n\times n}$  Boolean matrix ${\displaystyle M}$ . The algorithm then runs for ${\displaystyle n}$  rounds, and at each round ${\displaystyle i}$  receives an ${\displaystyle n}$ -dimensional Boolean vector ${\displaystyle v_{i}}$  and must return the product ${\displaystyle Mv_{i}}$  (before continuing to round ${\displaystyle i+1}$ ).^[1]

An algorithm is said to solve OMv if, with probability at least ${\displaystyle 2/3}$ , it returns the product ${\displaystyle Mv_{i}}$  at every round ${\displaystyle i}$ .

Variants of OMv

The online vector-matrix-vector problem (OuMv) is a variant of OMv where the algorithm receives, at each round ${\displaystyle i}$ , two Boolean vectors ${\displaystyle u_{i}}$  and ${\displaystyle v_{i}}$ , and returns the product ${\displaystyle u_{i}Mv_{i}}$ . This version has the benefit of returning a Boolean value at each round instead of a vector of an ${\displaystyle n}$ -dimensional Boolean vector. The hardness of OuMv is implied by the hardness of OMv.^[1]

More heavily parameterized variants of OMv are also used, where the matrix ${\displaystyle M}$  is not necessarily square and where the dimension of each vector ${\displaystyle v_{i}}$  is not necessarily equal to the number of rounds.

Conjectured hardness

In 2015, Henzinger, Krinninger, Nanongkai, and Saranurak conjectured that OMv cannot be solved in "truly subcubic" time.^[1] Formally, they presented the following conjecture:

For any constant ${\displaystyle \varepsilon >0}$ , there is no ${\displaystyle O(n^{3-\varepsilon })}$ -time algorithm that solves OMv with probability at least ${\displaystyle 2/3}$ .

Algorithms for solving OMv

OMv can be solved in ${\displaystyle O(n^{3})}$  time by a naive algorithm that, in each of the ${\displaystyle n}$  rounds, multiplies the matrix ${\displaystyle M}$  and the new vector ${\displaystyle v_{i}}$  in ${\displaystyle O(n^{2})}$  time. The fastest known algorithm for OMv is implied by a result of Williams and runs in time ${\displaystyle O(n^{3}/\log ^{2}n)}$ .^[2]

Implications of conjectured hardness

The OMv conjecture implies lower bounds on the time needed to solve a large class of dynamic graph problems, including reachability and connectivity, shortest path, and subgraph detection. For many of these problems, the implied lower bounds have matching upper bounds.^[1]

Later work showed that the OMv conjecture implies lower bounds on the time needed for subgraph counting in average-case graphs.^[3]

References

1. Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon; Saranurak, Thatchaphol. "Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture". Proceedings of the ACM Symposium on Theory of Computing. STOC '15. Association for Computing Machinery: 21–30. doi:10.1145/2746539.2746609. ISBN 978-1-4503-3536-2.
2. Williams, Ryan (2007-01-07). "Matrix-vector multiplication in sub-quadratic time: (some preprocessing required)". Proceedings of the ACM-SIAM Symposium on Discrete algorithms. SODA '07. USA: 995–1001. ISBN 978-0-89871-624-5.
3. Henzinger, Monika; Lincoln, Andrea; Saha, Barna. "The Complexity of Average-Case Dynamic Subgraph Counting". ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA '22: 459–498. doi:10.1137/1.9781611977073.23.