What can be sampled locally?

DOI10.1007/S00446-018-0332-8MaRDI QIDQ2189170zbMATHOpenAlexFDO

Authors Weiming Feng, Yitong Yin, Yuxin Sun

Publication date 15 June 2020

Published in Distributed Computing (Search for Journal in Brave)

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

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)

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.

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

Cites work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A constructive proof of the general Lovász local lemma
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A survey on the use of Markov chains to randomly sample colourings
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• An Improved Distributed Algorithm for Maximal Independent Set
• Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
• Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
• Counting in two-spin models on \(d\)-regular graphs
• Counting independent sets up to the tree threshold
• Deterministic \((\Delta+1)\)-coloring in sublinear (in \(\Delta\)) time in static, dynamic, and faulty networks
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed Computing: A Locality-Sensitive Approach
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed degree splitting, edge coloring, and orientations
• Distributed random walks
• Distributed verification and hardness of distributed approximation
• Dobrushin Conditions and Systematic Scan
• Finitary coloring
• Improved FPTAS for multi-spin systems
• Improved bounds for sampling colorings
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Information, Physics, and Computation
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• 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
• On Local Distributed Sampling and Counting
• On the complexity of distributed graph coloring
• On the complexity of local distributed graph problems
• Prescribing a System of Random Variables by Conditional Distributions
• Systematic scan for sampling colorings
• The locality of distributed symmetry breaking
• The price of being near-sighted
• Towards a complexity theory for local distributed computing
• Uniform sampling through the Lovász local lemma
• What Can be Computed Locally?
• What cannot be computed locally!
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Cited in

(7)

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

Describes a project that uses

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)