The Online Boolean Matrix-Vector Multiplication Conjecture
Prove or refute that for every epsilon > 0 there is no randomized algorithm which, given an n by n Boolean matrix and then n Boolean query vectors one at a time, outputs each Boolean-semiring product before receiving the next vector in total time O(n^(3-epsilon)) with error probability at most 1/3.
Status Open Status review date not recorded in this edition
Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.
References
Primary source
ProofAtlas open problems; Kasper Green Larsen and Ryan Williams, Faster Online Matrix-Vector Multiplication, arXiv:1605.01695v2 (2016), Conjecture 1.1.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.