Open Problems:75 - Revision history

Krzysztof Onak: Typo + formatting

2017-04-28T01:23:22Z

Typo + formatting

Blackc4 at 00:36, 2 April 2017

2017-04-02T00:36:56Z

Blackc4 at 22:31, 1 April 2017

2017-04-01T22:31:51Z

Blackc4: Created page with "{{Header |source=banff17 |who=Kasper Green Larsen }} Input is an $n \times n$ boolean matrix $M$. We can preprocess $M$ and store a data structure. Then on query $v$, an $n$..."

2017-03-31T17:53:40Z

Created page with "{{Header |source=banff17 |who=Kasper Green Larsen }} Input is an $n \times n$ boolean matrix $M$. We can preprocess $M$ and store a data structure. Then on query $v$, an $n$..."

New page

{{Header
|source=banff17
|who=Kasper Green Larsen
}}

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 Willimas {{cite|LW-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.

Question is, can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model?

<references />

@@ 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$.
-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.
+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 is, can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model for succinct data structures?
+'''Question:''' Can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model for succinct data structures?
 <references />

@@ 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$.
-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.
+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?
+Question is, can we show a lower bound of $\omega(n)$ on $t_q$ in the cell-probe model for succinct data structures?
 <references />