Content deleted Content added
m bolded oumv (I think this is the correct move since it's also like a title) |
m Open access bot: arxiv updated in citation with #oabot. |
||
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 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|arxiv=1511.06773 }}</ref> Formally, they presented the following conjecture:
{{Blockquote
Line 31:
=== 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 journal |last=Abboud |first=Amir |last2=Williams |first2=Virginia Vassilevska |title=Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems |url=https://ieeexplore.ieee.org/document/6979028 |journal=FOCS '14|pages=434–443 |doi=10.1109/FOCS.2014.53 |isbn=978-1-4799-6517-5|arxiv=1402.0054 }}</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 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>
| |||