Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PREFIX SUM:
Reports tagged with prefix sum:
TR09-054 | 7th June 2009
Emanuele Viola, Emanuele Viola

Cell-Probe Lower Bounds for Prefix Sums

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)} ... more >>>




ISSN 1433-8092 | Imprint