Content deleted Content added
→Example lower bounds: reachability |
m ce |
||
| (14 intermediate revisions by 8 users not shown) | |||
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 13:
=== Variants of OMv ===
The '''online vector-matrix-vector problem''' (OuMv) is a variant of OMv where the algorithm receives, at each round <math>i</math>, two Boolean vectors <math>u_i</math> and <math>v_i</math>, and returns the product <math>u_i M v_i</math>. This version has the benefit of returning a Boolean value at each round instead of a vector of an <math>n</math>-dimensional Boolean vector. The hardness of OuMv is implied by the hardness of OMv.<ref name=":0" />
More heavily parameterized variants of OMv are also used, where the matrix <math>M</math> is not necessarily square and where the dimension of each vector <math>v_i</math> is not necessarily equal to the number of rounds.
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.
|url=https://dl.acm.org/doi/10.5555/3039686.3039828 |journal=Proceedings of the ACM-SIAM Symposium on Discrete Algorithms |___location=USA |pages=2182–2189 |arxiv=1605.01695 |isbn= 978-1-61197-478-2}}</ref>
=== 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>{{
| | last2 = Williams | first2 = Virginia Vassilevska | title = 2014 IEEE 55th Annual Symposium on Foundations of Computer Science | chapter = Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems | | | doi = 10.1109/FOCS.2014.53 | | publisher = IEEE Computer Society
| year = 2014| isbn = 978-1-4799-6517-5
}}</ref> many of the lower bounds that follow from OMv are stronger or new.
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
====
Several lower bounds for dynamic problems follow from the OMv conjecture. Examples of tight lower bounds include the following.
* [[Pagh's problem]] on <math>k</math> subsets from a size-<math>n</math> universe requires linear time.<ref name=":0" />
* Determining s-t [[reachability]] for a (worst-case) dynamic graph on a graph with <math>n</math> nodes and <math>m\leq n^2</math> edges requires <math>\widetilde{\Omega}(m)</math> time.<ref name=":0" />
* Counting 4-cycles in average-case, dynamic graphs with <math>n</math> nodes requires <math>\widetilde{\Omega}(n^2)</math> time.<ref name=":1" />
* Counting length-5 paths in average-case, dynamic graphs with <math>n</math> nodes requires <math>\widetilde{\Omega}(n^3)</math> time.<ref name=":1" />
Line 48 ⟶ 57:
<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
{{reflist}}
{{Authority control}}
[[Category:Unsolved problems in computer science]]
[[Category:Computational problems]]
| |||