Online matrix-vector multiplication problem: Difference between revisions

Revision as of 08:41, 30 April 2024

Revision as of 08:44, 30 April 2024

Line 35:

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 lowerthe boundsOMv forconjecture subgraphimplies countinglower andbounds canon bethe extendedtime toneeded showfor hardnesssubgraph forcounting in [[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 ==