Optimal mixing for two-state anti-ferromagnetic spin systems
March 15, 2022 Β· Declared Dead Β· π IEEE Annual Symposium on Foundations of Computer Science
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang
arXiv ID
2203.07771
Category
math-ph
Cross-listed
cs.DS,
math.PR
Citations
31
Venue
IEEE Annual Symposium on Foundations of Computer Science
Last Checked
3 months ago
Abstract
We prove an optimal $Ξ©(n^{-1})$ lower bound for modified 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: $\bullet$ all strictly anti-ferromagnetic two-spin systems (where both edge parameters $Ξ²,Ξ³<1$), which cover the hardcore models and the anti-ferromagnetic Ising models; $\bullet$ general anti-ferromagnetic two-spin systems on regular graphs. Consequently, an optimal $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.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
π Similar Papers
In the same crypt β math-ph
R.I.P.
π»
Ghosted
R.I.P.
π»
Ghosted
Multivariate Trace Inequalities
R.I.P.
π»
Ghosted
Different quantum f-divergences and the reversibility of quantum operations
R.I.P.
π»
Ghosted
RΓ©nyi divergences as weighted non-commutative vector valued $L_p$-spaces
R.I.P.
π»
Ghosted
Uniqueness and characterization theorems for generalized entropies
R.I.P.
π»
Ghosted
A Proof of Vivo-Pato-Oshanin's Conjecture on the Fluctuation of von Neumann Entropy
Died the same way β π» Ghosted
R.I.P.
π»
Ghosted
Federated Learning: Strategies for Improving Communication Efficiency
R.I.P.
π»
Ghosted
In-Datacenter Performance Analysis of a Tensor Processing Unit
R.I.P.
π»
Ghosted
Deep Convolutional Neural Networks for Computer-Aided Detection: CNN Architectures, Dataset Characteristics and Transfer Learning
R.I.P.
π»
Ghosted