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

Leszek Gasieniec; Jesper Jansson; Christos Levcopoulos; Andrzej Lingas; Mia Persson

doi:10.1007/978-3-030-18126-0_14

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

Leszek Gasieniec, Jesper Jansson, Christos Levcopoulos, Andrzej Lingas, Mia Persson

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

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.

Original language	English
Title of host publication	Frontiers in Algorithmics
Subtitle of host publication	13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings
Publisher	Springer
Pages	156-169
Number of pages	14
ISBN (Electronic)	978-3-030-18126-0
ISBN (Print)	978-3-030-18125-3
DOIs	https://doi.org/10.1007/978-3-030-18126-0_14
Publication status	Published - 2019 Apr 9

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11458
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Subject classification (UKÄ)

Computer Science

Access to Document

10.1007/978-3-030-18126-0_14

Cite this

Gasieniec, L., Jansson, J., Levcopoulos, C., Lingas, A., & Persson, M. (2019). Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases. In Frontiers in Algorithmics : 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings (pp. 156-169). (Lecture Notes in Computer Science; Vol. 11458). Springer. https://doi.org/10.1007/978-3-030-18126-0_14

@inproceedings{fc31a0f285394908b28b72e546e84bc3,

title = "Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases",

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{\textquoteright}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.",

author = "Leszek Gasieniec and Jesper Jansson and Christos Levcopoulos and Andrzej Lingas and Mia Persson",

year = "2019",

month = apr,

day = "9",

doi = "10.1007/978-3-030-18126-0_14",

language = "English",

isbn = "978-3-030-18125-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "156--169",

booktitle = "Frontiers in Algorithmics",

address = "Germany",

}

Gasieniec, L, Jansson, J, Levcopoulos, C , Lingas, A & Persson, M 2019, Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases. in Frontiers in Algorithmics : 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11458, Springer, pp. 156-169. https://doi.org/10.1007/978-3-030-18126-0_14

Pushing the Online Matrix-Vector Conjecture Off-Line and Identifying Its Easy Cases. / Gasieniec, Leszek; Jansson, Jesper; Levcopoulos, Christos et al.
Frontiers in Algorithmics : 13th International Workshop, FAW 2019, Sanya, China, April 29 – May 3, 2019, Proceedings. Springer, 2019. p. 156-169 (Lecture Notes in Computer Science; Vol. 11458).

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

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

AU - Gasieniec, Leszek

AU - Jansson, Jesper

AU - Levcopoulos, Christos

AU - Lingas, Andrzej

AU - Persson, Mia

PY - 2019/4/9

Y1 - 2019/4/9

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.

U2 - 10.1007/978-3-030-18126-0_14

DO - 10.1007/978-3-030-18126-0_14

M3 - Paper in conference proceeding

SN - 978-3-030-18125-3

T3 - Lecture Notes in Computer Science

SP - 156

EP - 169

BT - Frontiers in Algorithmics

PB - Springer

ER -

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

Abstract

Publication series

Subject classification (UKÄ)

Access to Document

Fingerprint

Cite this