# 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