TY - GEN
T1 - Space-efficient local computation algorithms
AU - Alon, Noga
AU - Rubinfeld, Ronitt
AU - Vardi, Shai
AU - Xie, Ning
PY - 2012
Y1 - 2012
N2 - Recently Rubinfeld et al. (ICS 2011, pp. 223-238) 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 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 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.
AB - Recently Rubinfeld et al. (ICS 2011, pp. 223-238) 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 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 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.
UR - http://www.scopus.com/inward/record.url?scp=84860194094&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860194094&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973099.89
DO - 10.1137/1.9781611973099.89
M3 - Conference contribution
AN - SCOPUS:84860194094
SN - 9781611972108
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1132
EP - 1139
BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PB - Association for Computing Machinery
T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Y2 - 17 January 2012 through 19 January 2012
ER -