Log-concave Polynomials and Spectral Independence 1

on YouTube ↗01h 05m

" summary

Defines spectral independence as the largest eigenvalue of a conditional influence matrix and proves bounded η for all conditionals yields a spectral gap ≳ n^{-O(η)}, hence polynomial mixing of Glauber dynamics; with a graph factorization + bounded degree + nonvanishing marginals one gets a log-Sobolev type bound and n log n mixing. Tools include Dirichlet forms, couplings (sum of influences ≤ expected Hamming distance), and geometry of polynomials; examples: spanning trees give constant bounds, matchings give O(Δ) bounds.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to the topic
2. 4:33Glauber dynamics and mixing
3. 8:01Functional inequalities
4. 16:37Defining spectral independence
5. 24:06Analyzing independence
6. 30:13Theorems on spectral dependence
7. 37:30Verification techniques
8. 44:05High-dimensional expansion
9. 53:09Coupling for matching

" related talks

• 57mIt ain't over till it's overPei Wu · Beyond the Boolean Cube 2023
• 49mGeneralized Cheeger Inequalities and Constrained ClusteringIoannis Koutis · Fast Algorithms via Spectral Methods 2014
• 27mSharp Matrix ConcentrationMarch Boedihardjo · Deep Learning Theory Symposium 2021
• 56mSome Probabilistic Uses of Dirichlet EigenvectorsPersi Diaconis · Spectral Algorithms: From Theory to Practice 2014
• 36mThe Overlap Gap Property For Inference: Power And LimitationsIlias Zadik · Rigorous Evidence for Information-Computation Trade-offs
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 11mUnderstanding Statistical-to-Computational Gaps via Low-Degree PolynomialsAlex Wein · Meet the Fellows Welcome Event