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

Conjectured hardness

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

Implications of conjectured hardness

References

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

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

[1]