On Local Distributed Sampling and Counting

DOI10.1145/3212734.3212757MaRDI QIDQ5197683zbMATH OpenOpenAlexWikidataFDO

Authors Weiming Feng, Yitong Yin

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

Gibbs distributionlocal computationsampling algorithmsdistributed graph algorithmsstrong spatial mixing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Abstract: In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper ($Delta+1$)-list-colorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information. We study distributed sampling and counting problems, in which each instance specifies a joint distribution of feasible solutions. The task of distributed algorithm is to sample from this joint distribution, or to locally measure the volume of the probability space via the marginal probabilities. The latter task is also known as inference, which is a local counterpart of counting. For self-reducible classes of instances, the following equivalences are established in the LOCAL model up to polylogarithmic factors: $$ For all joint distributions, approximate inference and approximate sampling are computationally equivalent. $$ For all joint distributions defined by local constraints, exact sampling is reducible to either one of the above tasks. $$ If further, sequentially constructing a feasible solution is trivial locally, then all above tasks are easy if and only if the joint distribution exhibits strong spatial mixing. Combining with the state of the arts of strong spatial mixing, we obtain efficient sampling algorithms in the LOCAL model for various important sampling problems, including: an $O(sqrtDeltalo{g}^{3}n)$-round algorithm for exact sampling matchings in graphs with maximum degree $Delta$, and an $O(lo{g}^{3}n)$-round algorithm for sampling according to the hardcore model (weighted independent sets) in the uniqueness regime, which along with the $Omega(mathrmdiam)$ lower bound in arXiv:1702.00142 for sampling according to the hardcore model in the non-uniqueness regime, gives the first computational phase transition for distributed sampling.

Recommendations

• Approximate counting and sampling via local central limit theorems
• Computational Science - ICCS 2004
• Boosting distinct random sampling for basic counting on the union of distributed streams
• An inherent bottleneck in distributed counting
• Scalable Uniform Graph Sampling by Local Computation
• The counting pyramid: an adaptive distributed counting scheme
• Randomized algorithms for tracking distributed count, frequencies, and ranks
• Optimal Random Sampling from Distributed Streams Revisited
• Distributed counting along lossy paths without feedback
• Local-on-average distributed tasks

Cited in

(7)

• Exact distributed sampling
• Perfect sampling from spatial mixing
• An inherent bottleneck in distributed counting
• Perfect sampling for Gibbs point processes using partial rejection sampling
• Model counting meets \(F_0\) estimation
• What can be sampled locally?
• Parallelize single-site dynamics up to Dobrushin criterion

This page was built for publication: On Local Distributed Sampling and Counting

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