Editing Open Problems:75
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| 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 Willimas {{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 is, can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model for succinct data structures? | |
<references /> | <references /> | ||
