Online Matrix Vector Multiplication Hypothesis (OMV Hypothesis)
Revision as of 11:30, 15 February 2023 by Admin (talk | contribs) (Created page with "== Target Problem == OMV == 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/Citatio...")
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