Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction

DOI10.1137/20M136685XMaRDI QIDQ5885600zbMATH OpenOpenAlexFDO

Authors Zongchen Chen, Kuikui Liu, Eric Vigoda

Publication date 4 April 2023

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

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

zbMATH Keywords

approximate countingcorrelation decayGlauber dynamicsphase transitionsspectral independence

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Classical equilibrium statistical mechanics (general) (82B05) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Recommendations

• Fast mixing for independent sets, colorings, and other models on trees
• scientific article; zbMATH DE number 6469177
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime
• Correlation decay up to uniqueness in spin systems

Cites work

• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Approximate counting via correlation decay in spin systems
• Approximating partition functions of the two-state spin system
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Combinatorics and complexity of partition functions
• Correlation decay up to uniqueness in spin systems
• Counting in two-spin models on \(d\)-regular graphs
• Counting independent sets up to the tree threshold
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Fisher zeros and correlation decay in the Ising model
• scientific article; zbMATH DE number 3951995 (Why is no real title available?)
• Improved analysis of higher order random walks and applications
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Matchings and walks in graphs
• On a conjecture of Sokal concerning roots of the independence polynomial
• On trees with real-rooted independence polynomial
• Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
• Polynomial-Time Approximation Algorithms for the Ising Model
• Random generation of combinatorial structures from a uniform distribution
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
• Zeros of ferromagnetic 2-spin systems

Cited in

(13)

• Polymer dynamics via cliques: new conditions for approximations
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Algorithms for hard-constraint point processes via discretization
• Boolean function analysis on high-dimensional expanders
• Spectral independence via stability and applications to Holant-type problems
• Mixing on generalized associahedra
• Expanderizing higher-order random walks
• Glauber dynamics for the hard-core model on bounded-degree H-free graphs
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Fast and slow mixing of the Kawasaki dynamics on bounded-degree graphs
• Fast sampling via spectral independence beyond bounded-degree graphs
• Improved mixing of critical hardcore model
• Entropic independence via sparse localization

This page was built for publication: Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction

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