PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Local Computation Algorithms

Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie

arXiv:1104.1377v1cs.DS

TL;DR

The paper addresses how to compute selected parts of very large legal outputs without reading the entire input or output. It introduces consistent local computation algorithms and construction techniques based on locality and constructive Lovász Local Lemma analyses, obtaining polylogarithmic-time algorithms for several combinatorial problems. The work establishes concrete results for maximal independent set, radio broadcast scheduling, and hypergraph coloring while identifying limits on extending the approach to broader parallel algorithms.

  • Problem

    Very large inputs and outputs make complete computation impractical, motivating query access to selected output locations while maintaining consistency with one legal solution.

  • Method

    The paper defines local computation algorithms and combines locality-based simulation with Beck’s constructive Lovász Local Lemma analysis to answer output queries.

  • Results

    The framework yields polylogarithmic-time local algorithms for several problems, including an MIS algorithm with O(dO(d log d) · log n) query time and a broadcast algorithm with poly(∆) · log n query time.

  • Takeaways & Limitations

    The results show that consistent local query access can be obtained for selected combinatorial structures beyond the direct consequences of standard parallel algorithms.

  • Takeaways & Limitations

    The techniques do not extend to all problems covered by constructive Lovász Local Lemma proofs, and the local analogue of finding an even cycle in a balanced digraph remains unresolved.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces local computation algorithms for querying selected output locations consistently, unifying several local-computation paradigms and providing polylogarithmic-time construction techniques for multiple problems.

  • Motivation: Local computation algorithms answer queries to specified output locations without requiring the entire input or output to be processed.The model targets settings where both input and legal output may be too large for complete reading.
  • Unified framework: The proposed framework distills common features of local distributed computation, local algorithms, locally decodable codes, and local reconstruction.These fields differ in problem types, data access, and allowable running times.
  • Techniques: The main construction technique combines Beck’s algorithmic Lovász Local Lemma analysis with preprocessing that exposes problem locality.The technique is designed for polylogarithmic-time local computation algorithms.
  • Applications: For maximal independent set and radio broadcast scheduling, the approach uses the Parnas–Ron reduction from bounded-degree distributed algorithms to query-based simulation.The reduction simulates a specified node using O(Dt+1) input queries after t distributed rounds.
  • Applications: For hypergraph coloring and k-SAT, the approach modifies parallel Lovász Local Lemma algorithms and resolves most queries by simulating bounded-radius neighborhoods.Remaining queries are handled by brute force on very small subproblems using Beck’s analysis.
  • Limitations: Parallel O(log n)-time algorithms do not directly imply local algorithms through the Parnas–Ron reduction, leaving some Lovász Local Lemma problems unresolved.The paper specifically notes that applicability to more powerful Moser–Tardos algorithms remained unresolved.

2 Local Computation Algorithms: the model

The model gives randomized query access to a valid solution while requiring consistency across queries, and relates local computability to distributed algorithms, circuit depth, and locality-preserving reductions.

  • Model definition: The framework applies to large-input search problems and can also encompass function and optimization computations.The model does not require a specific input format and rules out computing the entire output first.
  • Model definition: A local computation algorithm answers each queried output location so that all answers are consistent with some valid solution.Its success probability is at least 1−δ over any query sequence, using local memory and a random tape.
  • Model definition: The model favors polylogarithmic dependence on input length, charges queries and processing time equally, and imposes no intrinsic restriction on input access.This generality can make it less appropriate for some distributed-algorithm applications.
  • Model properties: Query-oblivious algorithms make outputs depend only on the input and random tape, while parallelizable algorithms support parallel queries.These are separate properties defined by the model.
  • Relations to other models: Bounded-degree distributed algorithms and bounded-fan-in circuits yield local algorithms with query complexity governed by d^t, including NC0 ⊆ SLC.For distributed computation, the stated bound is d^t(n); for circuits, it is d(n)^t(n).
  • Relations to other models: The paper gives local algorithms for several NC1 problems but proves NC1 ⊈ SLC, so fast parallel computability does not generally guarantee local computability.The n-XOR problem illustrates the boundary because solving it requires reading all n inputs.
  • Locality-preserving reductions: Locality-preserving reductions compose local algorithms: if A reduces locally to B, A inherits B’s query time and failure probability with additive space overhead.The resulting bounds are t(n)·t′(n) time and s(n)+s′(n) space.

3 Preliminaries

The preliminaries establish notation for logarithms, natural numbers, graphs, neighborhoods, and degrees, then state the Lovász Local Lemma and define 3-trees used in later proofs.

  • Notation: All logarithms are base 2, and [n] denotes {1, …, n} for natural n ≥ 1.The paper also uses N for the nonnegative integers.
  • Graph notation: For an undirected graph, the paper defines vertex distance, neighborhoods, closed neighborhoods, and vertex degree.The closed neighborhood is N+(v)=N(v)∪{v}.
  • Lovász Local Lemma: The symmetric Lovász Local Lemma guarantees positive probability that none of a collection of dependent events occurs when ep(d+1) ≤ 1.Each event must have probability at most p and depend on at most d others.
  • Graph structures: A 3-tree is a vertex set whose pairwise distances are at least three and whose distance-three adjacency graph is connected.The auxiliary graph uses edges between pairs at graph distance exactly three.

4 Maximal Independent Set

The MIS local computation algorithm simulates Luby’s algorithm for O(d log d) rounds, then greedily resolves small surviving components to produce consistent maximal independent set answers. It achieves query time O(dO(d log d) · log n), linear space, and failure probability 1/n.

  • Overview: The algorithm decides whether a queried vertex belongs to a consistent maximal independent set through two phases.Phase 1 simulates Luby’s algorithm; Phase 2 explores and greedily solves the surviving component.
  • Theorem: The resulting local computation algorithm has query time O(dO(d log d) · log n), space O(n), and failure probability 1/n.The theorem guarantees consistent MIS answers for every vertex in a graph with maximum degree d.
  • Phase 1: simulating Luby’s parallel algorithm: Phase 1 simulates Luby’s algorithm for O(d log d) rounds, recursively evaluating neighboring vertices’ prior states.Each vertex is selected, deleted, or left in the surviving state ⊥; random bits are generated consistently when needed.
  • Phase 1: simulating Luby’s parallel algorithm: With probability at least 1 − 1/n, every connected component of surviving vertices after Phase 1 has size at most O(poly(d) · log n).The analysis uses Beck’s argument and a 3-tree bound to control surviving-component sizes.
  • Phase 2: Greedy search in the connected component: Phase 2 explores the surviving vertex component and applies greedy MIS when its size is at most c2 log n, otherwise returning Fail.The phase costs at most O(dO(d log d) · log n) because each component vertex requires a Phase 1 check.

5 Radio Networks

The section constructs local computation algorithms for radio-network broadcast schedules by computing an independent set cover, then applies the construction to obtain consistent broadcast functions. The resulting schedule uses O(∆2 log ∆) rounds with poly(∆) · log n query time, but has a quadratically larger round bound than Alon’s parallel algorithm.

  • A broadcast function assigns every vertex one transmission round, prevents multiple messages at any receiver in a round, and separates the rounds of adjacent vertices.
  • An independent set cover partitions vertices into pairwise disjoint independent sets whose indices define broadcast rounds.Vertices in each independent set broadcast in the same round; the resulting function satisfies the broadcast conditions.
  • The local algorithm computes an independent set cover of size O(d log d) consistently across vertex queries, using poly(d) · log n time and O(n) space with failure probability 1/n.It simulates Luby’s MIS algorithm for O(d log d) rounds and then greedily partitions surviving components.
  • After Phase 1, all surviving-vertex components have size at most O(poly(d) · log n) with probability at least 1 −1/n, enabling localized Phase 2 processing.If a component exceeds the prescribed threshold, the algorithm aborts; otherwise greedy partitioning adds at most d subsets.
  • Applying the independent-set-cover algorithm to the square graph G1,2 yields a consistent broadcast function using at most O(∆2 log ∆) rounds and poly(∆) · log n query time.The square graph connects vertices at distance one or two, so independent sets there enforce the separation needed for broadcasts.
  • The broadcast schedule uses a quadratically larger round bound than Alon’s parallel algorithm, and the paper does not show how to convert that algorithm into a local computation algorithm.

6 Hypergraph two-coloring

The section presents a local computation algorithm for two-coloring bounded-dependency hypergraphs, returning answers consistent with one valid coloring. It imitates Alon’s three-phase algorithm, explores local dependency components, and achieves polylogarithmic query time under stated parameter conditions.

  • 6.2 Overview of the coloring algorithm: The algorithm imitates Alon’s three phases: random coloring, recoloring surviving dependencies, and brute-force coloring of small remaining components.Phase 1 marks dangerous hyperedges and troubled vertices; later phases use increasingly restrictive thresholds before exhaustive search.
  • 6.4 Phase 2 coloring: Phase 2 explores the dependency graph around a trouble-1 vertex, repeatedly coloring correlated vertices and expanding the surviving hyperedge component.The exploration tracks surviving-1 hyperedges and associated uncolored vertices until no relevant hyperedges remain or the component exceeds a logarithmic threshold.
  • 6.4 Phase 2 coloring: Phase 2 and Phase 3 coloring each take at most polylogN time.These bounds support efficient responses to vertex-color queries after the algorithm identifies the relevant local dependency component.

7 k-CNF

The paper extends its hypergraph-coloring local computation approach to satisfying assignments of bounded-intersection k-CNF formulas. Under the stated parameter conditions, each variable query is answered consistently with some satisfying assignment in polylogarithmic time.

  • 7 k-CNF: The hypergraph coloring algorithm can be modified to compute satisfying assignments for k-CNF formulas with specified clause-intersection properties.The construction assumes fixed k and d and uses the same local dependency structure as the coloring algorithm.
  • 7 k-CNF: If each clause intersects at most d others and k, d satisfy the stated k1, k2, k3 conditions, the formula admits the paper’s local computation guarantee.The theorem applies to k-CNF formulas with k ≥ 2.
  • 7 k-CNF: With probability at least 1 − 1/N, the algorithm returns a consistent truth assignment for queried variables that agrees with some satisfying assignment of H.Consistency holds across any sequence of variable queries.
  • 7 k-CNF: Each variable query is answered in O((log N)^c) time, where c depends only on k and d.The proof sketch follows the hypergraph-coloring construction while changing the probability that a clause becomes dangerous-1 to 2^-k1.

8 Concluding Remarks and Open Problems

The paper introduces local computation algorithms and techniques for constructing them with polylogarithmic time and space. It leaves the scope of solvable problems and further techniques as open questions.

  • The paper proposes a model of local computation algorithms.
  • It gives techniques for constructing local computation algorithms with polylogarithmic time and space complexities.
  • The authors identify understanding the model’s scope and developing additional techniques as open problems.
Loading 1104.1377v1…