Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

Paul G. Allen School via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

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

Taught by

Paul G. Allen School

Reviews

Start your review of Theory Seminar - Spectral Independence in High-Dimensional Expanders, Kuikui Liu

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.