Advanced

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

Gasieniec, Leszek ; Jansson, Jesper LU ; Levcopoulos, Christos LU ; Lingas, Andrzej LU and Persson, Mia LU (2019) In Lecture Notes in Computer Science 11458. p.156-169
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Frontiers in Algorithmics : 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings - 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings
series title
Lecture Notes in Computer Science
volume
11458
pages
14 pages
publisher
Springer
external identifiers
  • scopus:85065315076
ISSN
1611-3349
0302-9743
ISBN
978-3-030-18126-0
978-3-030-18125-3
DOI
10.1007/978-3-030-18126-0_14
language
English
LU publication?
yes
id
fc31a0f2-8539-4908-b28b-72e546e84bc3
date added to LUP
2019-04-17 08:26:51
date last changed
2019-06-11 04:03:08
@inproceedings{fc31a0f2-8539-4908-b28b-72e546e84bc3,
  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].<br/><br/>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.},
  author       = {Gasieniec, Leszek and Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej and Persson, Mia},
  booktitle    = {Frontiers in Algorithmics  : 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings},
  isbn         = {978-3-030-18126-0},
  issn         = {1611-3349},
  language     = {eng},
  month        = {04},
  pages        = {156--169},
  publisher    = {Springer},
  series       = {Lecture Notes in Computer Science},
  title        = {Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases},
  url          = {http://dx.doi.org/10.1007/978-3-030-18126-0_14},
  doi          = {10.1007/978-3-030-18126-0_14},
  volume       = {11458},
  year         = {2019},
}