# Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication

arXiv: https://arxiv.org/abs/1711.04467 · HTML: https://mlsanity.com/paper/1711.04467/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2017.

## Built on by (most cited first, 4 of 4)

- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [Discovering Data Structures: Nearest Neighbor Search and Beyond](https://mlsanity.com/paper/2411.03253/) (2024)

## Abstract (arXiv)

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 tildeO(n7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional tildeO(n7/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 tildeO(n3/2) storing just tildeO(n3/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 < n2 must have query time t satisfying t r = tildeOmega(n3). For r ≤ n, any data structure must have t = tildeOmega(n2). 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 mathbbF2.