Online matrix-vector multiplication problem: Difference between revisions

Revision as of 13:43, 30 April 2024

Revision as of 21:20, 8 May 2024

Line 34:

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 bounds ====

Several lower bounds for dynamic problems, including those listed below, follow from the OMv conjecture.

* [[Pagh's problem]] on <math>k</math> subsets from a size-<math>n</math> universe requires linear time: that is, <math>\text{poly}(k,n)</math> pre-processing time, <math>k</math> updates, and <math>n</math> queries.<ref name=":0" />

* In the average case, Counting <math></math> ([[Average-case complexity|average-case]] counting of length-5 paths in a dynamic, random graph)

== References ==