Preprint
Exact Distributed Sampling
ArXiv.org
03/05/2023
DOI: 10.48550/arxiv.2303.02714
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 $O(\log n)$ 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 $O(\log n)$-round LOCAL model exact
sampling algorithms for a class of weighted local constraint satisfaction
problems. This general result leads to $O(\log n)$-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.
Details
- Title: Subtitle
- Exact Distributed Sampling
- Creators
- Sriram V PemmarajuJoshua Z Sobel
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2303.02714
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 03/05/2023
- Academic Unit
- Computer Science
- Record Identifier
- 9984410851402771
Metrics
9 Record Views