Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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 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.

Details

Authors
Organisations
External organisations
  • University of Liverpool
  • Hong Kong Polytechnic University
  • Malmö University
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science
Original languageEnglish
Title of host publicationFrontiers in Algorithmics
Subtitle of host publication13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings
PublisherSpringer
Pages156-169
Number of pages14
ISBN (Electronic)978-3-030-18126-0
ISBN (Print)978-3-030-18125-3
Publication statusPublished - 2019 Apr 9
Publication categoryResearch
Peer-reviewedYes

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11458
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349