Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤ 1/2+ε
Abstract
We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by λI (where λ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for β≤ 1/2+ε, for an absolute constant ε>0. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.
Related
- Optimal Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model at β< 1/2
- An Autonomous Spectral Representation for Fully Asymmetric Spherical Sherrington-Kirkpatrick Dynamics
- Sampling from the Sherrington-Kirkpatrick Model up to Criticality
- Free energy and fluctuations of generalized bipartite Sherrington-Kirkpatrick models and generalized Hopfield models
- Free energy fluctuation of soft spherical Sherrington-Kirkpatrick model
BibTeX
@misc{boban2026rank1perturbed,
title = {{Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac12+\varepsilon$}},
author = {Mathews Boban and Anqi Li and Shayan Oveis Gharan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13138},
eprint = {2609.13138},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13138},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤ 1/2+ε
AU - Mathews Boban
AU - Anqi Li
AU - Shayan Oveis Gharan
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.13138
UR - https://arxiv.org/abs/2609.13138
AB - We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by λI (where λ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for β≤ 1/2+ε, for an absolute constant ε>0. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.
ER -