Tight cell probe bounds for succinct boolean matrix-Vector multiplication

Diptarka Chakraborty; Lior Kamma; Kasper Green Larsen

doi:10.1145/3188745.3188830

Tight cell probe bounds for succinct boolean matrix-Vector multiplication

Diptarka Chakraborty, Lior Kamma, Kasper Green Larsen

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

9 Citations (Scopus)

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 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⁷/⁴) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional Õ(n⁷/⁴) 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³/²) storing just Õ(n³/²) 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² must have query time t satisfying tr = Ω (n³). For r ≤ n, any data structure must have t = Ω (n²). 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₂.

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 date	20 Jun 2018
Pages	1297-1306
ISBN (Electronic)	9781450355599
DOIs	https://doi.org/10.1145/3188745.3188830
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

Conference	50th Annual ACM Symposium on Theory of Computing, STOC 2018
Country/Territory	United States
City	Los Angeles
Period	25/06/2018 → 29/06/2018

Series	A C M Symposium on the Theory of Computing. Annual Proceedings
Number	2018
ISSN	0737-8017

Keywords

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

Access to Document

10.1145/3188745.3188830

https://arxiv.org/pdf/1711.04467.pdf

Cite this

@inproceedings{73782eb812bf4ba2823fe1c6a382415c,

title = "Tight cell probe bounds for succinct boolean matrix-Vector multiplication",

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{\textquoteright}15]. In recent work, Larsen and Williams [SODA{\textquoteright}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 {\~O}(n7/4) time and is succinct in the sense that it stores the input matrix in read-only memory, plus an additional {\~O}(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 {\~O}(n3/2) storing just {\~O}(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.",

keywords = "Boolean matrix-vector multiplication, Cell probe model, Lower bound, Succinct data structure",

author = "Diptarka Chakraborty and Lior Kamma and Larsen, {Kasper Green}",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188830",

language = "English",

series = "A C M Symposium on the Theory of Computing. Annual Proceedings",

publisher = "Association for Computing Machinery",

number = "2018",

pages = "1297--1306",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

address = "United States",

note = "50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

}

Chakraborty, D, Kamma, L & Larsen, KG 2018, Tight cell probe bounds for succinct boolean matrix-Vector multiplication. in STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, A C M Symposium on the Theory of Computing. Annual Proceedings, no. 2018, pp. 1297-1306, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States, 25/06/2018. https://doi.org/10.1145/3188745.3188830

Tight cell probe bounds for succinct boolean matrix-Vector multiplication. / Chakraborty, Diptarka; Kamma, Lior; Larsen, Kasper Green.
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, 2018. p. 1297-1306 (A C M Symposium on the Theory of Computing. Annual Proceedings; No. 2018).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

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 -

Tight cell probe bounds for succinct boolean matrix-Vector multiplication

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this