Cell-Probe Lower Bounds for Prefix Sums

Details Cell-Probe Lower Bounds for Prefix Sums Cell-Probe Lower Bounds for Prefix Sums

2009-06-07

arxiv.org/abs/0906.1370v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Cell-Probe Lower Bounds for Prefix Sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cell-Probe Lower Bounds for Prefix Sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cell-Probe Lower Bounds for Prefix Sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-370284