What can be sampled locally?

DOI10.1007/S00446-018-0332-8zbMATH Open1445.68334arXiv1702.00142OpenAlexW2801648136MaRDI QIDQ2189170FDOQ2189170

Authors: Weiming Feng, Yitong Yin, Yuxin Sun 

Publication date: 15 June 2020

Published in: Distributed Computing (Search for Journal in Brave)

Abstract: The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved locally: for a given local CSP whether a CSP solution can be constructed by a distributed algorithm using local information. In this paper, we consider the problem of sampling a uniform CSP solution by distributed algorithms, and ask whether a locally definable joint distribution can be sampled from locally. More broadly, we consider sampling from Gibbs distributions induced by weighted local CSPs in the LOCAL model. We give two Markov chain based distributed algorithms which we believe to represent two fundamental approaches for sampling from Gibbs distributions via distributed algorithms. The first algorithm generically parallelizes the single-site sequential Markov chain by iteratively updating a random independent set of variables in parallel, and achieves an $O(Deltalogn)$ time upper bound in the LOCAL model, where $Delta$ is the maximum degree, when the Dobrushin's condition for the Gibbs distribution is satisfied. The second algorithm is a novel parallel Markov chain which proposes to update all variables simultaneously yet still guarantees to converge correctly with no bias. It surprisingly parallelizes an intrinsically sequential process: stabilizing to a joint distribution with massive local dependencies, and may achieve an optimal $O(logn)$ time upper bound independent of the maximum degree $Delta$ under a stronger mixing condition. We also show a strong $Omega(diam)$ lower bound for sampling independent set in graphs with maximum degree $Deltage6$. This lower bound holds even when every node is aware of the graph. This gives a strong separation between sampling and constructing locally checkable labelings.

Full work available at URL: https://arxiv.org/abs/1702.00142

Recommendations

• What Can be Sampled Locally?
• On Local Distributed Sampling and Counting
• scientific article; zbMATH DE number 7561278
• What Can be Computed Locally?
• Scalable Uniform Graph Sampling by Local Computation

zbMATH Keywords

Markov chain Monte CarloGibbs samplinglocal computationLOCAL modeldistributed sampling algorithms

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Distributed algorithms (68W15)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Counting independent sets up to the tree threshold
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Prescribing a System of Random Variables by Conditional Distributions
• Improved bounds for sampling colorings
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• What cannot be computed locally!
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• A survey on the use of Markov chains to randomly sample colourings
• A constructive proof of the general Lovász local lemma
• Information, Physics, and Computation
• Distributed Random Walks
• Counting in two-spin models on \(d\)-regular graphs
• On the complexity of distributed graph coloring
• Distributed (∆+1)-coloring in sublogarithmic rounds
• Local Computation
• Systematic scan for sampling colorings
• The Locality of Distributed Symmetry Breaking
• The price of being near-sighted
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• Distributed algorithms for the Lovász local lemma and graph coloring
• What Can be Computed Locally?
• Finitary coloring
• Improved FPTAS for Multi-spin Systems
• An Improved Distributed Algorithm for Maximal Independent Set
• Towards a complexity theory for local distributed computing
• Dobrushin Conditions and Systematic Scan
• On Local Distributed Sampling and Counting
• Brief Announcement
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
• Distributed Degree Splitting, Edge Coloring, and Orientations
• On the complexity of local distributed graph problems
• Uniform sampling through the Lovasz local lemma

Cited In (7)

• Exact distributed sampling
• What Can be Sampled Locally?
• What Can be Computed Locally?
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Dynamic Sampling from Graphical Models
• Model counting meets \(F_0\) estimation
• What can be decided locally without identifiers?

Uses Software

• HOGWILD

This page was built for publication: What can be sampled locally?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189170)