Difference between revisions of "Open Problems:75"
(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$...") 
(No difference)

Revision as of 17:53, 31 March 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 wordRAM model, $t_p + nt_q \ge n^{3o(1)}$. But in the cellprobe model, Larsen and Willimas [LW17] 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 cellprobe model?