Content deleted Content added
→Definition: defined omv |
added info on fastest known alg |
||
Line 13:
The hardness of OMv was conjectured by Henzinger, Krinninger, Nanongkai, and Saranurak in 2015.<ref name=":0">{{Cite journal |last=Henzinger |first=Monika |last2=Krinninger |first2=Sebastian |last3=Nanongkai |first3=Danupon |last4=Saranurak |first4=Thatchaphol |title=Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture |url=https://doi.org/10.1145/2746539.2746609 |journal=Proceedings of the ACM Symposium on Theory of Computing |series=STOC '15 |publisher=Association for Computing Machinery |pages=21–30 |doi=10.1145/2746539.2746609 |isbn=978-1-4503-3536-2}}</ref>
The best-known algorithm for OMv is implied by 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 |publisher= |pages=995–1001 |isbn=978-0-89871-624-5}}</ref>
=== Implications of conjectured hardness ===
| |||