2 problems

Online Matrix–Vector conjecture. Computing $\mathbf{A}\boldsymbol{x}$ for general matrices cannot be done in truly sub-$mn$ time per multiplication.

Let $M\in\\{0,1\\}^{n\times n}$ be a matrix that is preprocessed, and let $v_1,\ldots,v_n\in\\{0,1\\}^n$ be presented online. The OMv conjecture. The total cost of preprocessing an…