Difference between revisions of "Open Problems:75"
m (Typo + formatting) |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 6: | Line 6: | ||
Input is an $n \times n$ boolean matrix $M$. We can preprocess $M$ and store a data structure. Then on query $v$, an $n$ bit vector, we need to output $Mv$, which is matrix multiplication with $\cdot$ replaced by $\wedge$ and $+$ replaced by $\vee$. The preprocessing time is denoted by $t_p$ and query time is denoted by $t_q$. | Input is an $n \times n$ boolean matrix $M$. We can preprocess $M$ and store a data structure. Then on query $v$, an $n$ bit vector, we need to output $Mv$, which is matrix multiplication with $\cdot$ replaced by $\wedge$ and $+$ replaced by $\vee$. The preprocessing time is denoted by $t_p$ and query time is denoted by $t_q$. | ||
| − | It is conjectured that in the word-RAM model, $t_p + nt_q \ge n^{3-o(1)}$. But in the cell-probe model, Larsen and | + | It is conjectured that in the word-RAM model, $t_p + nt_q \ge n^{3-o(1)}$. But in the cell-probe model, Larsen and Williams {{cite|LarsenW-17}} give a data structure that uses space $n^2 + n^{7/4}\sqrt{w}$, i.e., just $n^{7/4}\sqrt{w}$ extra bits, where $w$ is the word size (which is typically $\Theta(\log n)$). The data structure computes $Mv$ using $t_q = n^{7/4}/\sqrt{w}$ probes in the worst case. Such a data structure that stores only a small amount of extra bits is called a ''succinct'' data structure. |
| − | Question | + | '''Question:''' Can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model for succinct data structures? |
<references /> | <references /> | ||
Latest revision as of 01:23, 28 April 2017
| Suggested by | Kasper Green Larsen |
|---|---|
| Source | Banff 2017 |
| Short link | https://sublinear.info/75 |
Input is an $n \times n$ boolean matrix $M$. We can preprocess $M$ and store a data structure. Then on query $v$, an $n$ bit vector, we need to output $Mv$, which is matrix multiplication with $\cdot$ replaced by $\wedge$ and $+$ replaced by $\vee$. The preprocessing time is denoted by $t_p$ and query time is denoted by $t_q$.
It is conjectured that in the word-RAM model, $t_p + nt_q \ge n^{3-o(1)}$. But in the cell-probe model, Larsen and Williams [LarsenW-17] give a data structure that uses space $n^2 + n^{7/4}\sqrt{w}$, i.e., just $n^{7/4}\sqrt{w}$ extra bits, where $w$ is the word size (which is typically $\Theta(\log n)$). The data structure computes $Mv$ using $t_q = n^{7/4}/\sqrt{w}$ probes in the worst case. Such a data structure that stores only a small amount of extra bits is called a succinct data structure.
Question: Can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model for succinct data structures?
