Content deleted Content added
m Open access bot: arxiv updated in citation with #oabot. |
Citation bot (talk | contribs) Alter: journal, title, template type. Add: isbn, date, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Hilst | #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 |
== Definition ==
Line 19:
== Conjectured hardness ==
In 2015, Henzinger, Krinninger, Nanongkai, and Saranurak conjectured that OMv cannot be solved in "truly subcubic" time.<ref name=":0">{{Cite
{{Blockquote
Line 27:
=== Algorithms for solving OMv ===
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. The fastest known 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
=== Implications of conjectured hardness ===
The OMv conjecture implies lower bounds on the time needed to solve a large class of dynamic graph problems, including [[reachability]] and [[Connectivity (graph theory)|connectivity]], [[Shortest path problem|shortest path]], and subgraph detection. For many of these problems, the implied lower bounds have matching upper bounds.<ref name=":0" /> While some of these lower bounds also followed from previous conjectures (e.g., [[3SUM]]),<ref>{{Cite
Later work showed that the OMv conjecture implies lower bounds on the time needed for subgraph counting in [[Average-case complexity|average-case]] graphs.<ref name=":1">{{Cite journal |
==== Lower bounds from OMv ====
| |||