Online matrix-vector multiplication problem: Difference between revisions

Revision as of 08:08, 30 April 2024

Revision as of 08:41, 30 April 2024

Line 17:

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 theeach vector <math>v_i</math> is not necessarily equal to the number of rounds.

== Conjectured hardness ==

TheIn hardness of OMv was conjectured by2015, Henzinger, Krinninger, Nanongkai, and Saranurak conjectured that OMv cannot be solved in 2015"truly subcubic" time.<ref name=":0">{{Cite journal |last=Henzinger |first=Monika |last2=Krinninger |first2=Sebastian |last3=Nanongkai |first3=Danupon |last4=Saranurak |first4=Thatchaphol |title=Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture |url=https://doi.org/10.1145/2746539.2746609 |journal=Proceedings of the ACM Symposium on Theory of Computing |series=STOC '15 |publisher=Association for Computing Machinery |pages=21–30 |doi=10.1145/2746539.2746609 |isbn=978-1-4503-3536-2}}</ref> Formally, they presented the following conjecture:

{{Blockquote

Line 32:

=== 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" />

Later work showed that lower bounds for subgraph counting and can be extended to show hardness for [[Average-case complexity|average-case]] graphs.<ref name=":1">{{Cite journal |last=Henzinger |first=Monika |last2=Lincoln |first2=Andrea |last3=Saha|first3=Barna |title=The Complexity of Average-Case Dynamic Subgraph Counting |url=https://doi.org/10.1137/1.9781611977073.23 |journal=ACM-SIAM Symposium on Discrete Algorithms (SODA) |series=SODA '22 |pages=459–498 |doi=10.1137/1.9781611977073.23 }}</ref>

== References ==