Space-efficient local computation algorithms

Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie

Research output: Chapter in Book/Report/Conference proceedingConference contribution

49 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PublisherAssociation for Computing Machinery
Pages1132-1139
Number of pages8
ISBN (Print)9781611972108
DOIs
StatePublished - 2012
Externally publishedYes
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
CountryJapan
CityKyoto
Period1/17/121/19/12

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Space-efficient local computation algorithms'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Rubinfeld, R., Vardi, S., & Xie, N. (2012). Space-efficient local computation algorithms. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 (pp. 1132-1139). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.89