Space-efficient Local Computation Algorithms

Details Space-efficient Local Computation Algorithms Space-efficient Local Computation Algorithms

2011-09-28

arxiv.org/abs/1109.6178v2

Computer Science

Data Structures and Algorithms

Scientific paper

Recently Rubinfeld et al. (ICS 2011, pp. 223--238) proposed a new model of sublinear algorithms called \emph{local computation algorithms}. In this model, a computation problem $F$ may have more than one legal solution and each of them consists of many bits. The local computation algorithm for $F$ should answer in an online fashion, for any index $i$, the $i^{\mathrm{th}}$ bit of some legal solution of $F$. Further, all the answers given by the algorithm should be consistent with at least one solution of $F$. In this work, we continue the study of local computation algorithms. In particular, we develop a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time but also in polylogarithmic \emph{space}. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. Our main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.

Affiliated with

Also associated with

No associations

Rating

Space-efficient Local Computation Algorithms 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 Space-efficient Local Computation Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-efficient Local Computation Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-43557