TY - JOUR
T1 - Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases
AU - Gąsieniec, Leszek
AU - Jansson, Jesper
AU - Levcopoulos, Christos
AU - Lingas, Andrzej
AU - Persson, Mia
N1 - Funding Information:
Thanks go to the anonymous reviewers for their valuable comments. The authors were supported in part by Swedish Research Council grant 621-2017-03750 . JJ was also supported by PolyU Fund 1-ZE8L .
Publisher Copyright:
© 2021 Elsevier Inc.
PY - 2021/6
Y1 - 2021/6
N2 - 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.
AB - 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.
KW - Boolean matrix
KW - Dynamic graph problems
KW - Online computation
KW - Product of matrix and vector
KW - Time complexity
UR - http://www.scopus.com/inward/record.url?scp=85099348676&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85099348676&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2020.12.004
DO - 10.1016/j.jcss.2020.12.004
M3 - Article
AN - SCOPUS:85099348676
SN - 0022-0000
VL - 118
SP - 108
EP - 118
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
ER -