Content deleted Content added
Tags: Mobile edit Mobile web edit Advanced mobile edit |
Citation bot (talk | contribs) Add: isbn, volume, series. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
||
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 |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=287 |pages=62:1–62:25 |language=en |doi=10.4230/LIPIcs.ITCS.2024.62|doi-access=free |isbn=978-3-95977-309-6 }}</ref>
== Definition ==
| |||