Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-054 | 7th June 2009 00:00

Cell-Probe Lower Bounds for Prefix Sums

RSS-Feed




TR09-054
Authors: Emanuele Viola, Emanuele Viola
Publication: 2nd July 2009 11:20
Downloads: 1480
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint