Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
From MaRDI portal
Publication:2656173
DOI10.1016/j.jcss.2020.12.004zbMath1477.68122WikidataQ113871641 ScholiaQ113871641MaRDI QIDQ2656173
Andrzej Lingas, Jesper Jansson, Mia Persson, Christos Levcopoulos, Leszek Gąsieniec
Publication date: 10 March 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2020.12.004
time complexity; Boolean matrix; online computation; dynamic graph problems; product of matrix and vector
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
15B34: Boolean and Hadamard matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 3D rectangulations and geometric matrix multiplication
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Dynamic Steiner Tree Problem
- Faster Online Matrix-Vector Multiplication
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Tight cell probe bounds for succinct Boolean matrix-vector multiplication
- Algorithms and Data Structures