Explore the Glauber Dynamics algorithm for sampling from the hardcore model in this 27-minute IEEE conference talk. Delve into the concept of up-to-uniqueness rapid mixing, examining its application to 2-spin systems. Learn about the hardcore model as a weighted independent set problem, the uniqueness threshold, and the classic Markov Chain Monte Carlo method. Discover known results for both ferromagnetic and antiferromagnetic cases, and understand the proof approach using self-avoiding walk trees. Gain insights into influences on SAW trees and their implications for rapid mixing in spin systems.
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
Overview
Syllabus
Intro
Hardcore Model = Weighted Independent Sets
Sampling from Hardcore Model
Uniqueness Threshold
Glauber Dynamics A classic, simple Markov Chain Monte Carlo (MCMC) method In each step: 1. Pick a vertex v uniformly at random 2. Update a conditioned on all other vertices
Known Results (Ferromagnetic)
Known Results (Antiferromagnetic)
Spin Systems The hardcore model and Ising model belong to the family of 2-spin systems
Spin Systems (Cont.)
Up-to-A Uniqueness
Proof Approach
Self-Avoiding Walk Tree
Example
Influences on SAW Tree (Cont.)
Conclusion
Taught by
IEEE FOCS: Foundations of Computer Science
