Lune

FOCS2022顶会

Optimal mixing for two-state anti-ferromagnetic spin systems

Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang

2022年份
15被引次数
14顶会引用

摘要

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.

问问这篇 Paper

智能体会读完全文。

Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

引用它的顶会 Paper14

问问它们各自怎么用它

它引用的顶会 Paper9

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖