Tight cell probe bounds for succinct Boolean matrix-vector multiplication

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 Õ( n 7/4 ) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional Õ( 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 Õ( n 3/2 ) storing just Õ( 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 = Ω( n 3 ). For r ≤ n , any data structure must have t = Ω( 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 F 2 .

Authors

• Diptarka Chakraborty
• Lior Kamma
• Kasper Green Larsen

Keywords

• Boolean matrix-vector multiplication
• Cell probe model
• Lower bound
• Succinct data structure