Online matrix-vector multiplication problem: Difference between revisions

Revision as of 21:20, 8 May 2024

Revision as of 21:57, 8 May 2024

Line 36:

==== Example lower bounds ====

Several lower bounds for dynamic problems, including those listed below, follow from the OMv conjecture. Examples of tight lower bounds include the following.

* [[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)

* Counting 4-cycles in average-case, dynamic graphs on <math>n</math> nodes requires <math>\widetilde{\Omega}(n^2)</math> time.<ref name=":1" />

== References ==