Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
Publication:2656173
DOI10.1016/j.jcss.2020.12.004zbMath1477.68122OpenAlexW3118551000WikidataQ113871641 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Boolean and Hadamard matrices (15B34)
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
This page was built for publication: Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases