Online matrix-vector multiplication problem

Unsolved problem in computer science

Is there an algorithm for solving the OMv problem in time $O(n^{3-\varepsilon })$, for some constant $\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 $n\times n$ matrix and a newly-arrived $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 $n$ and an $n\times n$ Boolean matrix $M$. The algorithm then runs for $n$ rounds, and at each round $i$ receives an $n$-dimensional Boolean vector $v_{i}$ and must return the product $Mv_{i}$ (before continuing to round $i+1$).

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

Variants of OMv

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

More heavily parameterized variants of OMv are also used, where the matrix is not necessarily square and where the dimension of the vector is not necessarily equal to the number of rounds.

Conjectured hardness

The hardness of OMv was conjectured by Henzinger, Krinninger, Nanongkai, and Saranurak in 2015. Formally, they presented the following conjecture:

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

Algorithms for solving OMv

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