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 ${\mathcal {A}}$ is said to solve OMv if, with probability at least $2/3$, it returns the product $Mv_{i}$ at every round $i$.

Conjectured hardness

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

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 algorithm for OMv is implied by a result of Williams and runs in time $O(n^{3}/\log ^{2}n)$.