Perfect sampling from spatial mixing
From MaRDI portal
Publication:6052473
DOI10.1002/rsa.21079arXiv1907.06033OpenAlexW4213070169MaRDI QIDQ6052473
Heng Guo, Yitong Yin, Weiming Feng
Publication date: 17 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.06033
Sampling theory, sample surveys (62D05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Counting in two-spin models on \(d\)-regular graphs
- Finitary codings for spatial mixing Markov random fields
- Random generation of combinatorial structures from a uniform distribution
- On weak mixing in lattice models
- Random cluster dynamics for the Ising model is rapidly mixing
- Counting hypergraph matchings up to uniqueness threshold
- Mixing properties and exponential decay for lattice systems in finite volumes.
- Perfect sampling using bounding chains.
- Exact thresholds for Ising-Gibbs samplers on general graphs
- Perfect simulation of the hard disks model by partial rejection sampling
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Improved bounds for sampling colorings
- Random sampling for the monomer–dimer model on a lattice
- Randomly coloring constant degree graphs
- Counting independent sets up to the tree threshold
- Approximating the Permanent
- Information, Physics, and Computation
- Exact sampling from anti‐monotone systems
- Randomly coloring graphs with lower bounds on girth and maximum degree
- Probability
- The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
- Mixing in time and space for lattice spin systems: A combinatorial view
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Approximately counting bases of bicircular matroids
- Tight bounds for popping algorithms
- Improved bounds for perfect sampling of k-colorings in graphs
- On Local Distributed Sampling and Counting
- Dynamic sampling from graphical models
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- Improved Bounds for Randomly Sampling Colorings via Linear Programming
- Uniform Sampling Through the Lovász Local Lemma
- Strong spatial mixing of list coloring of graphs
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
- Correlation Decay up to Uniqueness in Spin Systems
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
- Perfectly sampling k ≥ (8/3 + o (1))Δ-colorings in graphs