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 ${\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 vector ${\displaystyle v_{i}}$  and must return the product ${\displaystyle Mv_{i}}$  (before continuing to round ${\displaystyle i+1}$ ).^[1]

An algorithm ${\displaystyle {\mathcal {A}}}$  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}$ .

Conjectured hardness

The hardness of OMv was conjectured by Henzinger, Krinninger, Nanongkai, and Saranurak in 2015.^[1]

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 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

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.