Exact distributed sampling
From MaRDI portal
Publication:6148084
DOI10.1007/978-3-031-32733-9_25arXiv2303.02714OpenAlexW4377971957MaRDI QIDQ6148084
Sriram V. Pemmaraju, Unnamed Author
Publication date: 11 January 2024
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2303.02714
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Counting in two-spin models on \(d\)-regular graphs
- Random generation of combinatorial structures from a uniform distribution
- Approximate counting, uniform generation and rapidly mixing Markov chains
- What can be sampled locally?
- Toward Optimal Bounds in the Congested Clique
- Counting independent sets up to the tree threshold
- Local Computation
- The Locality of Distributed Symmetry Breaking
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Exact Sampling from a Continuous State Space
- An Improved Distributed Algorithm for Maximal Independent Set
- An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- On Exact Simulation of Markov Random Fields Using Coupling from the Past
- Uniform sampling through the Lovasz local lemma
- Improved bounds for perfect sampling of k-colorings in graphs
- On Local Distributed Sampling and Counting
- What can be computed locally?
- MST in Log-Star Rounds of Congested Clique
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- What cannot be computed locally!
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Perfectly sampling k ≥ (8/3 + o (1))Δ-colorings in graphs
This page was built for publication: Exact distributed sampling