Content deleted Content added
created draft for omv problem |
m constant eps |
||
Line 1:
{{Short description|Problem in computational complexity theory}}
{{unsolved|computer science|Is there an algorithm for solving the OMv problem in time <math>O(n^{3-\varepsilon})</math>, for some constant <math>\varepsilon>0</math>?}}
In [[computational complexity theory]], the '''online matrix-vector multiplication problem''' (OMv) asks an online algorithm to return, at each round, the product of an <math>n\times n</math> matrix and a newly-arrived <math>n</math>-dimensional vector. OMv is conjectured to require roughly cubic time. This conjectured hardness implies lower bounds on the time needed to solve various [[Dynamic problem (algorithms)|dynamic problems]] and is of particular interest in [[Fine-grained reduction|fine-grained complexity]].
| |||