Pushing the online matrix-vector conjecture off-line and identifying its easy cases



Gąsieniec, L ORCID: 0000-0003-1809-9814, Jansson, J, Levcopoulos, C, Lingas, A and Persson, M
(2019) Pushing the online matrix-vector conjecture off-line and identifying its easy cases .

[thumbnail of pomvelfaw.pdf] Text
pomvelfaw.pdf - Author Accepted Manuscript

Download (203kB) | Preview

Abstract

© Springer Nature Switzerland AG 2019. 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.

Item Type: Conference Item (Unspecified)
Uncontrolled Keywords: 46 Information and Computing Sciences
Depositing User: Symplectic Admin
Date Deposited: 12 Jun 2019 10:17
Last Modified: 22 May 2026 19:38
DOI: 10.1007/978-3-030-18126-0_14
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3045521
Disclaimer: The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.