Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases

Gąsieniec, Leszek ORCID: 0000-0003-1809-9814, Jansson, Jesper, Levcopoulos, Christos, Lingas, Andrzej and Persson, Mia (2021) Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases. Journal of Computer and System Sciences, 118. pp. 108-118.

Text
OMV.pdf - Author Accepted Manuscript
Download (330kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.jcss.2020.12.004

Abstract

Henzinger et al. posed the so-called Online Boolean Matrix-vector Multiplication (OMv) conjecture and showed that it implies tight hardness results for several basic dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of the matrix or the input vectors are clustered, and develop new efficient randomized algorithms for such cases. Finally, we present applications of our algorithms to answering graph queries.

Item Type:	Article
Uncontrolled Keywords:	Boolean matrix, Product of matrix and vector, Dynamic graph problems, Online computation, Time complexity
Depositing User:	Symplectic Admin
Date Deposited:	10 Mar 2021 08:55
Last Modified:	18 Jan 2023 22:56
DOI:	10.1016/j.jcss.2020.12.004
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3116914