Content deleted Content added
→Definition: added info on variants of omv |
m →Conjectured hardness: added new header for best known omv algs |
||
Line 26:
|text=For any constant <math>\varepsilon</math>, there is no <math>O(n^{3-\varepsilon})</math>-time algorithm that solves OMv with probability at least <math>2/3</math>.
}}
=== 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. The fastest known 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 |publisher= |pages=995–1001 |isbn=978-0-89871-624-5}}</ref>
| |||