  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 $\tilde{O}(n^{7/4})$ time and is succinct in the
sense that it stores the input matrix in read-only memory, plus an additional
$\tilde{O}(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 $\tilde{O}(n^{3/2})$
storing just $\tilde{O}(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 $t r =
\tilde{\Omega}(n^3)$. For $r \leq n$, any data structure must have $t =
\tilde{\Omega}(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$.
