TY - GEN
T1 - Tight cell probe bounds for succinct boolean matrix-Vector multiplication
AU - Chakraborty, Diptarka
AU - Kamma, Lior
AU - Larsen, Kasper Green
PY - 2018/6/20
Y1 - 2018/6/20
N2 - 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 Õ(n7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional Õ(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 Õ(n3/2) storing just Õ(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 tr = Ω (n3). For r ≤ n, any data structure must have t = Ω (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 F2.
AB - 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 Õ(n7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional Õ(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 Õ(n3/2) storing just Õ(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 tr = Ω (n3). For r ≤ n, any data structure must have t = Ω (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 F2.
KW - Boolean matrix-vector multiplication
KW - Cell probe model
KW - Lower bound
KW - Succinct data structure
UR - http://www.scopus.com/inward/record.url?scp=85049906996&partnerID=8YFLogxK
U2 - 10.1145/3188745.3188830
DO - 10.1145/3188745.3188830
M3 - Article in proceedings
AN - SCOPUS:85049906996
T3 - A C M Symposium on the Theory of Computing. Annual Proceedings
SP - 1297
EP - 1306
BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -