Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Submitted manuscript
Final published version
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.
Original language | English |
---|---|
Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |
Number of pages | 10 |
Publisher | Association for Computing Machinery |
Publication year | 20 Jun 2018 |
Pages | 1297-1306 |
ISBN (Electronic) | 9781450355599 |
DOIs | |
Publication status | Published - 20 Jun 2018 |
Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 |
Conference | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|
Land | United States |
By | Los Angeles |
Periode | 25/06/2018 → 29/06/2018 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |
Series | A C M Symposium on the Theory of Computing. Annual Proceedings |
---|---|
Number | 2018 |
ISSN | 0737-8017 |
See relations at Aarhus University Citationformats
ID: 131963911