Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy CasesShow others and affiliations
2019 (English)In: Frontiers in Algorithmics: 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings / [ed] Yijia Chen, Xiaotie Deng, Mei Lu, Springer, 2019, p. 156-169Conference paper, Published paper (Refereed)
Abstract [en]
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.
Place, publisher, year, edition, pages
Springer, 2019. p. 156-169
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11458
Keywords [en]
Boolean matrix, Product of matrix and vector, Dynamic graph problems, Online computation, Time complexity
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-64600DOI: 10.1007/978-3-030-18126-0_14Scopus ID: 2-s2.0-85065315076ISBN: 978-3-030-18125-3 (print)ISBN: 978-3-030-18126-0 (electronic)OAI: oai:DiVA.org:mau-64600DiVA, id: diva2:1821053
Conference
13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019
2023-12-192023-12-192023-12-28Bibliographically approved