Online matrix-vector multiplication problem: Difference between revisions

Revision as of 09:04, 24 September 2024

Revision as of 14:23, 18 December 2024

Line 3:

{{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]].<ref name=":1" /><ref name=":0" /><ref>{{Cite journal |last1=Henzinger |first1=Monika |last2=Saha |first2=Barna |last3=Seybold |first3=Martin P. |last4=Ye |first4=Christopher |date=2024 |title=On the Complexity of Algorithms with Predictions for Dynamic Graph Problems |journal=Itcs '24 |pages=62:1–62:25 |language=en |doi=10.4230/LIPIcs.ITCS.2024.62|doi-access=free }}</ref>

== Definition ==

Line 28:

OMv can be solved in <math>O(n^3)</math> time by a naive algorithm that, in each of the <math>n</math> rounds, multiplies the matrix <math>M</math> and the new vector <math>v_i</math> in <math>O(n^2)</math> time. A faster algorithm for OMv is implied by a result of Williams and runs in time <math>O(n^3/\log^2 n)</math>.<ref>{{Cite journal |last=Williams |first=Ryan |date=2007-01-07 |title=Matrix-vector multiplication in sub-quadratic time: (some preprocessing required) |url=https://dl.acm.org/doi/10.5555/1283383.1283490 |journal=Proceedings of the ACM-SIAM Symposium on Discrete Algorithms |series=SODA '07 |___location=USA |pages=995–1001 |isbn=978-0-89871-624-5}}</ref> The fastest known algorithm for OMv runs in time <math>n^3/2^{\Omega{\sqrt{\log n}}}</math>, due to Larsen and Williams.<ref>{{Cite journal |last1=Larsen |first1=Kasper Green |last2=Williams |first2=Ryan |date=2017-01-16 |title=Faster online matrix-vector multiplication

|url=https://dl.acm.org/doi/10.5555/3039686.3039828 |journal=Proceedings of the ACM-SIAM Symposium on Discrete Algorithms |series=SODA '17 |___location=USA |pages=2182–2189 |arxiv=1605.01695 |isbn= 978-1-61197-478-2}}</ref>

=== Implications of conjectured hardness ===