ECCC-Report TR09-054https://eccc.weizmann.ac.il/report/2009/054Comments and Revisions published for TR09-054en-usThu, 02 Jul 2009 11:20:00 +0300
Paper TR09-054
| Cell-Probe Lower Bounds for Prefix Sums |
Emanuele Viola,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2009/054We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.
Our bound matches a recent upper bound of n +
n/log^{Omega(q)} n by Patrascu (FOCS 2008), also
non-adaptive.
We also obtain a n + n/log^{2^{O(q)}} n lower bound for
storing a string of balanced brackets so that each
Match(i) query can be answered by non-adaptively probing q
cells. To obtain these bounds we show that a too efficient
data structure allows us to break the correlations between
query answers.
Thu, 02 Jul 2009 11:20:00 +0300https://eccc.weizmann.ac.il/report/2009/054