Abstract: Fast distributed algorithms that output a feasible solution for constraint satisfaction problems, such as maximal independent sets, have been heavily studied. There has been much less research on distributed sampling problems, where one wants to sample from a distribution over all feasible solutions (e.g., uniformly sampling a feasible solution). Recent work (Feng, Sun, Yin PODC 2017; Fischer and Ghaffari DISC 2018; Feng, Hayes, and Yin arXiv 2018) has shown that for some constraint satisfaction problems there are distributed Markov chains that mix in rounds in the classical LOCAL model of distributed computation. However, these methods return samples from a distribution close to the desired distribution, but with some small amount of error. In this paper, we focus on the problem of exact distributed sampling. Our main contribution is to show that these distributed Markov chains in tandem with techniques from the sequential setting, namely coupling from the past and bounding chains, can be used to design -round LOCAL model exact sampling algorithms for a class of weighted local constraint satisfaction problems. This general result leads to -round exact sampling algorithms that use small messages (i.e., run in the CONGEST model) and polynomial-time local computation for some important special cases, such as sampling weighted independent sets (aka the hardcore model) and weighted dominating sets.
Cites work
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- An Improved Distributed Algorithm for Maximal Independent Set
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Counting in two-spin models on \(d\)-regular graphs
- Counting independent sets up to the tree threshold
- Exact Sampling from a Continuous State Space
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- scientific article; zbMATH DE number 1775385 (Why is no real title available?)
- scientific article; zbMATH DE number 7561278 (Why is no real title available?)
- Improved bounds for perfect sampling of k-colorings in graphs
- Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
- 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.
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- MST in \(O(1)\) rounds of congested clique
- MST in log-star rounds of congested clique
- On Exact Simulation of Markov Random Fields Using Coupling from the Past
- On Local Distributed Sampling and Counting
- Perfectly sampling k ≥ (8/3 + o (1))Δ-colorings in graphs
- Random generation of combinatorial structures from a uniform distribution
- The locality of distributed symmetry breaking
- Toward optimal bounds in the congested clique, graph connectivity and MST
- Uniform sampling through the Lovász local lemma
- What can be computed locally?
- What can be sampled locally?
- What cannot be computed locally!
This page was built for publication: Exact distributed sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148084)
