Revision as of 22:15, 8 May 2024 edit Palindromesemordnilap (talk \| contribs) Extended confirmed users 4,912 edits →Example lower bounds: reachability Tag: Visual edit ← Previous edit		Revision as of 22:22, 8 May 2024 edit undo Palindromesemordnilap (talk \| contribs) Extended confirmed users 4,912 edits m renamed subsection Tag: Visual edit Next edit →
Line 35: 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> ==== ~~Example lower~~Lower bounds from OMv ==== Several lower bounds for dynamic problems follow from the OMv conjecture. Examples of tight lower bounds include the following.

Online matrix-vector multiplication problem: Difference between revisions