Theory Seminar - Spectral Independence in High-Dimensional Expanders, Kuikui Liu

Explore a theory seminar on spectral independence in high-dimensional expanders and its applications to the hardcore model. Delve into Kuikui Liu's presentation, which demonstrates how spectrally independent probability distributions relate to local spectral expanders in high-dimensional simplicial complexes. Learn about the implications for rapid mixing of Glauber dynamics and efficient sampling from these distributions. Discover the groundbreaking application to the hardcore model, showing polynomial-time mixing of Glauber dynamics up to the uniqueness threshold, improving upon previous quasi-polynomial time algorithms. Gain insights into topics such as Markov chain decomposition, Garland's method for local spectral expansion, weak spatial mixing, and tree recurrence. Engage with open-ended problems and future research directions in this 55-minute lecture from the Paul G. Allen School, complete with closed captions.

Intro
A Natural Algorithm
Spectral Independence (cont.)
Application: The Hardcore Model
Why care about the Hardcore Model?
A Physical Phase Transition
A Complexity Phase Transition
Outline
Simplicial Complex from u
X for the Hardcore Model
Markov Chain Decomposition
Proof Strategy
Garland's Method for Local Spectral Expansion
Weak Spatial Mixing
Spatial Mixing and Spectral Independence on zd
Rough Strategy
The Tree Recurrence
Bounding Each Vertex Separately
Induction on Levels
Open-Ended Problems
Open Problems for Hardcore Model