TY - GEN
T1 - Pushing the online matrix-vector conjecture off-line and identifying its easy cases
AU - Ga̧sieniec, Leszek
AU - Jansson, Jesper Andreas
AU - Levcopoulos, Christos
AU - Lingas, Andrzej
AU - Persson, Mia
PY - 2019/1/1
Y1 - 2019/1/1
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 partially dynamic or dynamic problems [STOC’15]. We show that the OMv conjecture is implied by a simple off-line conjecture. If a not uniform (i.e., it might be different for different matrices) polynomial-time preprocessing of the matrix in the OMv conjecture is allowed then we can show such a variant of the OMv conjecture to be equivalent to our off-line conjecture. On the other hand, we show that the OMV conjecture does not hold in the restricted cases when the rows of the matrix or the input vectors are clustered.
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 partially dynamic or dynamic problems [STOC’15]. We show that the OMv conjecture is implied by a simple off-line conjecture. If a not uniform (i.e., it might be different for different matrices) polynomial-time preprocessing of the matrix in the OMv conjecture is allowed then we can show such a variant of the OMv conjecture to be equivalent to our off-line conjecture. On the other hand, we show that the OMV conjecture does not hold in the restricted cases when the rows of the matrix or the input vectors are clustered.
UR - http://www.scopus.com/inward/record.url?scp=85065315076&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-18126-0_14
DO - 10.1007/978-3-030-18126-0_14
M3 - Conference article published in proceeding or book
AN - SCOPUS:85065315076
SN - 9783030181253
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 156
EP - 169
BT - Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings
A2 - Chen, Yijia
A2 - Deng, Xiaotie
A2 - Lu, Mei
PB - Springer-Verlag
T2 - 13th International Workshop on Frontiers in Algorithmics, FAW 2019
Y2 - 29 April 2019 through 3 May 2019
ER -