Online matrix-vector multiplication problem: Difference between revisions

Revision as of 10:42, 23 April 2025

Latest revision as of 00:52, 11 August 2025

(One intermediate revision by the same user not shown)

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 book |last1=Henzinger |first1=Monika |last2=Krinninger |first2=Sebastian |last3=Nanongkai |first3=Danupon |last4=Saranurak |first4=Thatchaphol |chapter=Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture |title=Proceedings of the forty-seventh annual ACM symposium on Theory of Computing |chapter-url=https://doi.org/10.1145/2746539.2746609 |series=STOC '15 |date=2015 |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 27:

=== Algorithms for solving OMv ===

OMv can be solved in <math>O(n^3)</math> time by a naive algorithm that, in each of the <math>n</math> rounds, multiplies the matrix <math>M</math> and the new vector <math>v_i</math> in <math>O(n^2)</math> time. A faster algorithm for OMv is implied by a result of Williams and runs in time <math>O(n^3/\log^2 n)</math>.<ref>{{Cite journal |last=Williams |first=Ryan |date=2007-01-07 |title=Matrix-vector multiplication in sub-quadratic time: (some preprocessing required) |url=https://dl.acm.org/doi/10.5555/1283383.1283490 |journal=Proceedings of the ACM-SIAM Symposium on Discrete Algorithms |series=SODA '07 |___location=USA |pages=995–1001 |isbn=978-0-89871-624-5}}</ref> The fastest known algorithm for OMv runs in time <math>n^3/2^{\Omega{\sqrt{\log n}}}</math>, due to Larsen and Williams.<ref>{{Cite journal |last1=Larsen |first1=Kasper Green |last2=Williams |first2=Ryan |date=2017-01-16 |title=Faster online matrix-vector multiplication

|url=https://dl.acm.org/doi/10.5555/3039686.3039828 |journal=Proceedings of the ACM-SIAM Symposium on Discrete Algorithms |series=SODA '17 |___location=USA |pages=2182–2189 |arxiv=1605.01695 |isbn= 978-1-61197-478-2}}</ref>

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

| last1 = Abboud | first1 = Amir

| last2 = Williams | first2 = Virginia Vassilevska | author2-linktitle = Virginia2014 VassilevskaIEEE Williams55th Annual Symposium on Foundations of Computer Science

| chapter = Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems

| author2-link = Virginia Vassilevska Williams

| arxiv = 1402.0054

| contribution = Popular conjectures imply strong lower bounds for dynamic problems

| doi = 10.1109/FOCS.2014.53

| pages = 434–443

| publisher = IEEE Computer Society

| title = 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014

| year = 2014| isbn = 978-1-4799-6517-5

}}</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 journalbook |last1=Henzinger |first1=Monika |last2=Lincoln |first2=Andrea |last3=Saha|first3=Barna |title=Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |chapter=The Complexity of Average-Case Dynamic Subgraph Counting |chapter-url=https://doi.org/10.1137/1.9781611977073.23 |journal=ACM-SIAM Symposium on Discrete Algorithms (SODA) |series=SODA '22 |date=2022 |pages=459–498 |doi=10.1137/1.9781611977073.23 |isbn=978-1-61197-707-3 }}</ref>

==== Lower bounds from OMv ====