Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model

DOI10.1137/17M1127144zbMath1422.68272arXiv1604.01422OpenAlexW2942571798WikidataQ127965229 ScholiaQ127965229MaRDI QIDQ4634031

Charilaos Efthymiou, Yitong Yin, Eric Vigoda, Thomas P. Hayes, Daniel Štefanković

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

Markov chain Monte CarloGibbs samplingloopy belief propagationhard-core modelrapid mixing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Spectral independence, coupling, and the spectral gap of the Glauber dynamics, What can be sampled locally?, Complexity results for MCMC derived from quantitative bounds, The Ising partition function: zeros and deterministic approximation, Algorithms for #BIS-Hard Problems on Expander Graphs, Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions, Mixing of Markov chains for independent sets on chordal graphs with bounded separators, Belief propagation on the random \(k\)-SAT model, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Dynamic Sampling from Graphical Models

Cites Work

• Unnamed Item
• Unnamed Item
• Counting in two-spin models on \(d\)-regular graphs
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• On the hardness of sampling independent sets beyond the tree threshold
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• A note on the Glauber dynamics for sampling independent sets
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Improved mixing condition on the grid for counting and sampling independent sets
• Approximation algorithms for the normalizing constant of Gibbs distributions
• Spatial mixing and the connective constant: optimal bounds
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions
• Local uniformity properties for glauber dynamics on graph colorings
• Randomly coloring constant degree graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• FPTAS for #BIS with Degree Bounds on One Side
• The Complexity of Approximating a Bethe Equilibrium
• Counting Independent Sets Using the Bethe Approximation
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Randomly coloring planar graphs with fewer colors than the maximum degree
• The Complexity of Enumeration and Reliability Problems
• Fast convergence of the Glauber dynamics for sampling independent sets
• Balls and bins: A study in negative dependence
• On the Uniqueness of Loopy Belief Propagation Fixed Points
• On Markov Chains for Independent Sets
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• A Simple FPTAS for Counting Edge Covers
• Probability and Computing
• Correlation Decay up to Uniqueness in Spin Systems
• Approximate Counting via Correlation Decay in Spin Systems