The Online Boolean Matrix-Vector Multiplication Conjecture

The Online Boolean Matrix-Vector Multiplication Conjecture

Definitions and mathematical statement

The Boolean product of a matrix $M\in\{0,1\}^{n\times n}$ and a vector $v\in\{0,1\}^n$ is defined by \[ (Mv)_i=\bigvee_{j=1}^n(M_{ij}\wedge v_j). \] An online algorithm receives $M$, then $n$ vectors $v^{(1)},\ldots,v^{(n)}$ sequentially, and must output $Mv^{(t)}$ before receiving the next vector. The online matrix--vector multiplication conjecture rules out, for every fixed ${\varepsilon}>0$, a randomized algorithm of total time $O(n^{3-{\varepsilon}})$ and bounded error at most $1/3$ in the source's experiment. Matrix preprocessing is included in the total-time accounting of this formulation. Offline multiplication, in which all vectors are known at once, does not meet this information constraint. The bounded-error convention must be used consistently when specifying the entire output sequence.

Formulation and concept references: [S1].

Short English statement

Can one multiply a Boolean matrix by an online sequence of vectors in genuinely subcubic total time, while answering each vector before seeing the next?

Research attempt

Status: UNRESOLVED. Explicit online algorithms give logarithmic savings and faster bounds for structured matrices or query streams. A direct reduction to dynamic reachability is proved with preprocessing and error accounting. These do not produce a fixed power saving for arbitrary matrices, and no matching unconditional computational lower bound is obtained.

Source audit and computational model.

The primary source [S1], consulted on 27 September 2026, states the OMV conjecture and gives an algorithm with a subpolynomial improvement factor, as well as a stronger improvement when only memory probes are charged. The latter model makes computation free and is not a disproof of the ordinary running-time conjecture. This attempt uses conventional word-RAM accounting with words of order $\log n$ bits and polynomial-size memory. Reading the matrix, preprocessing it, and producing every answer are included.

A Boolean sum is an OR, not addition modulo two. Two witnesses to an output bit reinforce each other rather than cancel. An algorithm for parity matrix multiplication therefore needs an additional argument before it applies to this problem. Likewise, putting all query vectors into a matrix and invoking offline fast matrix multiplication violates the requirement to answer the first vector before the later vectors are available.

1. Baseline and a word-parallel saving.

The direct algorithm computes each of $n$ output coordinates by scanning a row of $M$, using order $n^2$ operations per vector and order $n^3$ for the sequence. If rows and the current vector are packed into $w$-bit words, an output coordinate is one exactly when some word of their bitwise intersection is nonzero. This costs $O(\lceil n/w\rceil)$ operations per row, hence \[ O(n^2+n^3/w) \] operations for preprocessing and $n$ queries, with the $n^2$ term allowing input and output overhead. For $w=\Theta(\log n)$ this is $O(n^3/\log n+n^2)$.

This does not contradict the conjecture. For every fixed $\varepsilon>0$, $n^\varepsilon/\log n\to\infty$, so the displayed upper bound is not $O(n^{3-\varepsilon})$. Allowing a word of $n$ bits and charging its intersection as one operation would change the model; it cannot be used silently to turn this calculation into quadratic time.

2. A table algorithm with fully counted preprocessing.

Partition the columns into blocks of length at most $b$. For each block and each subset $S$ of its columns, store the $n$-bit vector \[ T(S)=\bigvee_{j\in S}M_{*,j}. \] The empty subset has the zero vector. Build all other entries from a smaller subset by adding one column, requiring $O(n)$ elementary coordinate operations per entry. There are $O(n/b)$ blocks, so preprocessing costs \[ O\left(n^2+\frac{n^2 2^b}{b}\right). \] For a new vector $v$, read its selected-column subset in each block, retrieve the corresponding table vector, and OR those vectors. The result is exactly $Mv$. This uses $O(n+n^2/b)$ operations per query, while respecting the online order.

Choose $b=\max(1,\lfloor\tfrac12\log_2 n\rfloor)$. The total cost for all queries is \[ O\left(n^2+\frac{n^{5/2}}{\log n}+\frac{n^3}{\log n}\right) =O(n^3/\log n+n^2) \] for large $n$. Tables and addresses have polynomial size and fit the stated word-RAM convention. This derivation deliberately does not claim additional word-packing improvements.

Taking $b$ to be a positive power of $n$ would accelerate queries but make $2^b$ preprocessing superpolynomial. Taking $b$ of order $\log n$ keeps tables affordable but yields only a logarithmic factor. The preprocessing tradeoff is the precise obstruction in this elementary approach.

3. Complete fast subcases.

If $M$ has $s$ ones, scan the incident entries of each row and OR the corresponding query coordinates. Including output initialization gives $O(s+n)$ time per query and \[ O(n^2+ns) \] for the whole sequence. Thus matrices with $s=O(n^{2-\delta})$ admit a fixed power improvement, but the conjecture ranges over dense matrices too.

If $M$ has only $d$ distinct rows, identify the rows by a binary trie in $O(n^2)$ time. Compute the answer once for each distinct row and copy it to the appropriate positions. The total cost is $O(n^2+n^2d)$. This is again faster when $d$ is much smaller than $n$, without addressing matrices having $n$ distinct dense rows.

If a Boolean factorization $M=U V$ of inner dimension $r$ is supplied, with multiplication over the Boolean semiring, associativity gives \[ Mv=U(Vv). \] Direct evaluation takes $O(nr+n)$ per query, hence $O(n^2r+n^2)$ overall. This assumes that the factorization is given or constructed within the claimed total time. Existence of a small factorization is not by itself an efficient method for finding it from $M$.

Finally, if only $d$ distinct query vectors occur, cache each answer after its first computation, using a trie to recognize repeated vectors in $O(n)$ time. The total is $O(dn^2+n^2)$. The algorithm does not need advance knowledge of future queries, but its good bound depends on their repetition. None of these restricted inputs covers the general dense, unstructured online case.

4. A concrete dynamic-reachability consequence.

Create a directed graph with row vertices $r_1,\ldots,r_n$, column vertices $c_1,\ldots,c_n$, and a target $t$. Insert the static arc $r_i\to c_j$ exactly when $M_{ij}=1$. For the current vector $v$, maintain an arc $c_j\to t$ exactly when $v_j=1$. There are no other arcs. Then \[ r_i\text{ reaches }t\quad\Longleftrightarrow\quad(Mv)_i=1. \] Each new vector needs at most $n$ changes to the target arcs, followed by $n$ reachability queries, all completed before reading the next vector. Over the full sequence there are $O(n^2)$ updates and $O(n^2)$ reachability queries, and the static graph has $O(n^2)$ arcs.

If the dynamic structure has preprocessing $P(n)$ and amortized update/query bounds $U(n),Q(n)$ over such operation sequences, this gives total time \[ O\left(n^2+P(n)+n^2(U(n)+Q(n))\right). \] Thus, for example, truly subcubic preprocessing together with $U+Q=O(n^{1-\delta})$ for a fixed $\delta>0$ would give a truly subcubic OMV algorithm. This is a conditional consequence of a hypothesized data structure, not a lower bound proved without the OMV conjecture. Cubic preprocessing would already exhaust the desired time budget, however fast its later queries were.

5. Error probability belongs to the entire experiment.

There are $n^2$ output bits. A guarantee of error at most $1/3$ separately for each bit does not imply that the whole sequence is correct with probability at least $2/3$. For a fixed input stream, independent repetition and majority vote can reduce a per-answer error below $1/(3n^2)$ with $O(\log n)$ repetitions, after which a union bound controls all answers. A logarithmic repetition factor preserves a fixed polynomial saving after reducing its exponent slightly.

For an adaptive input stream, one needs a guarantee that remains valid under that adaptivity, for example a suitable conditional error bound. A guarantee proved only for each fixed stream cannot be promoted automatically by using the same stored randomness against queries chosen from earlier random outputs. The deterministic algorithms above avoid this issue; a randomized reduction must specify the experiment to which its guarantee applies.

6. Why an information-counting shortcut does not prove cubic time.

The answers to the $n$ standard basis queries reveal every column of $M$. Hence a lossless representation capable of answering all possible queries distinguishes $2^{n^2}$ matrices and needs at least $n^2$ bits in the worst case. This is a storage argument. It does not say that every query must inspect $n^2$ bits: the standard basis queries themselves can be answered by copying one column, in $O(n)$ time each.

A stateful online algorithm may also organize information learned in earlier queries. A lower bound for a separately built circuit for one fixed matrix-vector product does not automatically sum over $n$ queries in such an algorithm. The source's cell-probe result is a further warning that counting retrieved information alone cannot justify the desired computational bound in that more permissive model.

The faster algorithm in [S1] has total time of the form $n^3/2^{\Omega(\sqrt{\log n})}$ for a sequence of length $n$. Its saving exceeds any fixed logarithmic power but remains $n^{o(1)}$. It therefore still has exponent $3-o(1)$ and leaves the fixed-$\varepsilon$ target untouched.

7. Finite diagnostics and the missing general argument.

The offline script exhaustively compares the direct Boolean product, block-table product and layered-graph reachability answers for all matrices through dimension three and all query vectors. It checks supplied small Boolean factorizations and verifies that ordinary parity multiplication can disagree, retaining a concrete negative example. These are exact bit calculations; their purpose is to validate the reductions and restricted algorithms, not to infer asymptotic lower bounds from timings.

A solution must either give a fixed power improvement while charging all preprocessing and respecting every online deadline, or prove that every randomized algorithm in the specified model fails to do so. The algorithms and reductions above do neither for arbitrary inputs. The OMV conjecture remains unresolved here.

Sources

• S1 Kasper Green Larsen and Ryan Williams, Faster Online Matrix-Vector Multiplication, arXiv:1605.01695v2 $2016$, Conjecture 1.1. https://people.csail.mit.edu/virgi/6.1420/papers/omvalg.pdf. Formulation source.