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 this talk, we discuss the cell probe complexity (that is, we only charge for memory accesses, while computation is free) of Boolean matrix-vector multiplication. In a recent work, Larsen and Williams [SODA'17] attacked the problem from the upper bound side and gave a surprising cell probe data structure. Their cell probe data structure answers queries in O(n^7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional O(n^7/4) bits on the side. In this talk we present 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 = Omega(n^3). For r ? n, any data structure must have t = 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 complement the lower bound with a new succinct cell probe data structure with query time O(n^3/2) storing just O(n^3/2) bits on the side.