Online matrix–vector multiplication

Imagine a table recording direct connections from three starting points to three destinations. The first starting point connects to destinations 1 and 2, the second to 2 and 3, and the third to none. A query marks a selection of destinations and asks which starting points connect to at least one selected destination. Selecting only destination 2 gives yes, yes, no. The next selection arrives only after that answer has been returned. Can a general algorithm handle a growing sequence of these queries with a fixed improvement over checking the whole table each time?[1]

Online Boolean matrix–vector multiplication asks how fast a fixed connection table can answer selections revealed one at a time, without waiting for later selections. Store the table in $M\in\{0,1\}^{n\times n}$ and a selection in $v\in\{0,1\}^n$. The Boolean product uses AND to test a connection to a selected column and OR to combine the tests: $(Mv)_i=\bigvee_{j=1}^{n}(M_{ij}\land v_j)$. For the illustrative matrix with rows $(1,1,0)$, $(0,1,1)$, $(0,0,0)$, selection $v=(0,1,0)$ gives $Mv=(1,1,0)$; selection $(0,0,1)$ gives $(0,1,0)$. These are direct-connection answers, not arbitrary path searches. In OMv, $n$ vectors arrive and each answer must precede the next vector. The conjecture excludes a total-time bound $O(n^{3-\varepsilon})$ for fixed $\varepsilon>0$, even for randomized algorithms whose probability of an erroneous computation is at most $1/3$. Total time includes preparing the matrix.[1]

No such general speedup is established, even allowing bounded-error randomness.[1]

The target concerns arbitrary Boolean matrices and the entire online computation. Faster multiplication on matrices with a bounded structural parameter does not suffice. In the cited February 2026 revision, bounds depend on a measure of the column patterns present across rows; this restriction can make selected input families easier without supplying a uniform fixed power saving on all matrices. Allowing later vectors to be known in advance also changes the problem.[1] [2]

Answering as requests arrive prevents an algorithm from reorganizing all future requests together. That restriction also appears when a graph changes and a program must answer queries before the next change. The conjecture connects this simple table task to conditional limits on how cheaply certain dynamic graph algorithms can combine updates with answers.[1]

OMv’s Boolean product can be interpreted as testing intersections between a row’s connections and a query’s selected destinations. Reductions turn such tests into sequences of graph updates and queries, transferring a forbidden total-time speedup into restrictions on update/query costs if the conjecture holds. The source also develops variants that permit polynomial preprocessing; their conditional bounds account for that model separately. This is why the online requirement and the accounting for preparation matter as much as the matrix arithmetic.[1]