Online Matrix Vector Multiplication Hypothesis (OMV Hypothesis)
Jump to navigation
Jump to search
Target Problem
Description
Every (randomized) algorithm that can process a given $n \times n$ Boolean matrix $A$, and then in an online way can compute the products $Av_i$ for any $n$ vectors $v_1,\ldots,v_n$, must take total time $n^{3-o(1)}$.
Implies the following Hypothesis
Implied by the following Hypothesis
Computation Model
Word-Ram on $\log(n)$ bit words
Proven?
No
Year
References/Citation
http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 9