Aarhus University Seal

Faster Online Matrix-Vector Multiplication

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an nfin Boolean matrix M, we receive n Boolean vectors v1; : : : ;vn one at a time, and are required to output Mvi (over the Boolean semiring) before seeing the vector vi+1, for all i. Previous known algorithms for this problem are combinatorial, running in O(n 3=log 2 n) time. Henzinger et al. conjecture there is no O(n 3-ϵ ) time algorithm for OMV, for all e > 0; their OMV conjecture is shown to imply strong hardness results for many basic dynamic problems. We give a substantially faster method for computing OMV, running in n 3=2W( p logn) randomized time. In fact, after seeing 2w( p logn) vectors, we already achieve n2=2W( p logn) amortized time for matrix-vector multiplication. Our approach gives a way to reduce matrix-vector multiplication to solving a version of the Orthogonal Vectors problem, which in turn reduces to "small" algebraic matrix-matrix multiplication. Applications include faster independent set detection, partial match retrieval, and 2-CNF evaluation. We also show how a modification of our method gives a cell probe data structure for OMV with worst case O(n7=4= p w) time per query vector, where w is the word size. This result rules out an unconditional proof of the OMV conjecture using purely information-theoretic arguments.

Original languageEnglish
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
Number of pages9
PublisherSociety for Industrial and Applied Mathematics
Publication year2017
ISBN (Electronic)978-1-61197-478-2
Publication statusPublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) - Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017
Conference number: 28


Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

See relations at Aarhus University Citationformats

ID: 107977676