Lune

FOCS2022Top-tier venue

Optimal mixing for two-state anti-ferromagnetic spin systems

Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang

2022Year
15Citations
14Top-tier citations

Abstract

We prove an optimal Ω(n−1)\Omega(n^{-1}) lower bound for modified log⁡\log-Sobolev (MLS) constant of the Glauber dynamics for anti-ferromagnetic two-spin systems with n vertices in the tree uniqueness regime. Specifically, this optimal MLS bound holds for the following classes of two-spin systems in the tree uniqueness regime: (1) all strictly anti-ferromagnetic two-spin systems (where both edge parameters β,γ≤\beta, \gamma\leq 1), which cover the hardcore models and the anti-ferromagnetic Ising models; (2) general antiferromagnetic two-spin systems on regular graphs. Consequently, an optimal O(nlog⁡n)O(n\log n) mixing time holds for these anti-ferromagnetic two-spin systems when the uniqueness condition is satisfied. These MLS and mixing time bounds hold for any bounded or unbounded maximum degree, and the constant factors in the bounds depend only on the gap to the uniqueness threshold. We prove this by showing a boosting theorem for MLS constant for distributions satisfying certain spectral independence and marginal stability properties.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

Cited by top-tier papers14

Ask how each one uses it

Builds on9

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines