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

Conjectured hardness

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

The best-known algorithm for OMv is implied by Williams and runs in time $O(n^{3}/\log ^{2}n)$.