Tight cell probe bounds for succinct Boolean matrix-vector multiplication

DOI10.1145/3188745.3188830MaRDI QIDQ5230382zbMATH OpenOpenAlexFDO

Authors Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.04467

zbMATH Keywords

Boolean matrix-vector multiplicationcell probe modellower boundsuccinct data structure

Mathematics Subject Classification ID

Boolean and Hadamard matrices (15B34) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The conjectured hardness of Boolean matrix-vector multiplication has been used with great success to prove conditional lower bounds for numerous important data structure problems, see Henzinger et al. [STOC'15]. In recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure (that is, we only charge for memory accesses, while computation is free). Their cell probe data structure answers queries in $ildeO(n^{7/4})$ time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional $ildeO(n^{7/4})$ bits on the side. In this paper, we essentially settle the cell probe complexity of succinct Boolean matrix-vector multiplication. We present a new cell probe data structure with query time $ildeO(n^{3/2})$ storing just $ildeO(n^{3/2})$ bits on the side. We then complement our data structure with a lower bound showing that any data structure storing $r$ bits on the side, with $n<r<n^2$ must have query time $t$ satisfying $tr=ildeOmega(n^3)$. For $rleqn$, any data structure must have $t=ildeOmega(n^2)$. Since lower bounds in the cell probe model also apply to classic word-RAM data structures, the lower bounds naturally carry over. We also prove similar lower bounds for matrix-vector multiplication over $mathbb{F}_2$.

Recommendations

• The cell probe complexity of succinct data structures
• Faster Online Matrix-Vector Multiplication
• Cell probe lower bounds for succinct data structures
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

Cited in

(7)

• A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
• Pushing the online matrix-vector conjecture off-line and identifying its easy cases
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
• Orthogonal vectors indexing
• On the complexity of algorithms with predictions for dynamic graph problems
• Time/space tradeoffs for generic attacks on delay functions

This page was built for publication: Tight cell probe bounds for succinct Boolean matrix-vector multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230382)