Fast Local Computation Algorithms

Abstract

For input $x$, let $F(x)$ denote the set of outputs that are the "legal" answers for a computational problem $F$. Suppose $x$ and members of $F(x)$ are so large that there is not time to read them in their entirety. We propose a model of {\em local computation algorithms} which for a given input $x$, support queries by a user to values of specified locations $y_i$ in a legal output $y\in F(x)$. When more than one legal output $y$ exists for a given $x$, the local computation algorithm should output in a way that is consistent with at least one such $y$. Local computation algorithms are intended to distill the common features of several concepts that have appeared in various algorithmic subfields, including local distributed computation, local algorithms, locally decodable codes, and local reconstruction. We develop a technique, based on known constructions of small sample spaces of $k$-wise independent random variables and Beck's analysis in his algorithmic approach to the Lov{á}sz Local Lemma, which under certain conditions can be applied to construct local computation algorithms that run in {\em polylogarithmic} time and space. We apply this technique to maximal independent set computations, scheduling radio network broadcasts, hypergraph coloring and satisfying $k$-SAT formulas.

A preliminary version of this paper appeared in ICS 2011, pp. 223-238

Cited by in corpus (10)

• The Locality of Distributed Symmetry Breaking
• Federated Bandit: A Gossiping Approach
• A Local Computation Approximation Scheme to Maximum Matching
• Provably efficient, succinct, and precise explanations
• Learning Concepts Definable in First-Order Logic with Counting
• A Faster Local Algorithm for Detecting Bounded-Size Cuts with Applications to Higher-Connectivity Problems
• Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
• Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
• Spectral Clustering Oracles in Sublinear Time
• Black-box Methods for Restoring Monotonicity