Online matrix-vector multiplication problem: Difference between revisions

Revision as of 21:57, 8 May 2024

Revision as of 22:15, 8 May 2024

Line 38:

Several lower bounds for dynamic problems 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" />

* Determining s-t [[reachability]] for a (worst-case) dynamic graph on a graph with <math>n</math> nodes and <math>m\leq n^2</math> edges requires <math>\widetilde{\Omega}(m)</math> time.<ref name=":0" />

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

* Counting length-5 paths in average-case, dynamic graphs with <math>n</math> nodes requires <math>\widetilde{\Omega}(n^3)</math> time.<ref name=":1" />

== References ==