Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases

Gasieniec, Leszek ; Jansson, Jesper LU ; Levcopoulos, Christos LU orcid ; Lingas, Andrzej LU and Persson, Mia LU (2021) In Journal of Computer and System Sciences 118. p.108-118
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 dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of... (More)
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 dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of the matrix or the input vectors are clustered, and develop new efficient randomized algorithms for such cases. Finally, we present applications of our algorithms to answering graph queries. (Less)
Abstract (Swedish)
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 dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of... (More)
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 dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of the matrix or the input vectors are clustered, and develop new efficient randomized algorithms for such cases. Finally, we present applications of our algorithms to answering graph queries. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Boolean matrix, Product of matrix and vector, Dynamic graph problems, Online computation, Time complexity
in
Journal of Computer and System Sciences
volume
118
pages
11 pages
publisher
Academic Press
external identifiers
  • scopus:85099348676
ISSN
0022-0000
DOI
10.1016/j.jcss.2020.12.004
language
English
LU publication?
yes
id
e72af51a-5533-4e76-ab42-a2c7d94bf3bc
date added to LUP
2021-01-13 19:25:17
date last changed
2025-01-11 03:13:09
@article{e72af51a-5533-4e76-ab42-a2c7d94bf3bc,
  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 dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of the matrix or the input vectors are clustered, and develop new efficient randomized algorithms for such cases. Finally, we present applications of our algorithms to answering graph queries.}},
  author       = {{Gasieniec, Leszek and Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej and Persson, Mia}},
  issn         = {{0022-0000}},
  keywords     = {{Boolean matrix; Product of matrix and vector; Dynamic graph problems; Online computation; Time complexity}},
  language     = {{eng}},
  pages        = {{108--118}},
  publisher    = {{Academic Press}},
  series       = {{Journal of Computer and System Sciences}},
  title        = {{Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases}},
  url          = {{http://dx.doi.org/10.1016/j.jcss.2020.12.004}},
  doi          = {{10.1016/j.jcss.2020.12.004}},
  volume       = {{118}},
  year         = {{2021}},
}