CATS-Apr-3-2015
Title[edit]
Space-efficient Local Computation Algorithms
Speaker[edit]
Brian Brubach
Abstract[edit]
This talk is based on the paper "Space-efficient Local Computation Algorithms" by Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. No prior knowledge of Local Computation Algorithms is required.
Rubinfeld et al. proposed a new model of sublinear algorithms called 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 ith 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 talk, we'll see 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 space. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. The main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.
