Log-concave Polynomials and Spectral Independence 2

on YouTube ↗01h 00m

" summary

Shows that log-concavity of g_mu and explicit zero-free region around 1 each imply spectral independence by translating marginals and pairwise influences into first and second derivatives of log g_mu, so operator norm of the influence matrix is bounded (proof gives O(delta^2) in the stated setting). Uses complex analysis (Schwarz–Pick style bound) by building maps phi and C so a univariate holomorphic f recovers influences, and uses Asano–Ruelle contractions to prove multivariate zero-freeness for matchings and spanning trees by reducing to quadratic checks via successive contractions.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 1:39Polynomials and spectral independence
3. 7:19Key properties for spectral independence
4. 11:20Log concavity meaning
5. 17:26Proving log concavity via trickle down
6. 21:15Spanning trees example
7. 24:40Zero freeness approach
8. 26:57Zero free regions and spectral independence
9. 30:33Complex analysis for zero freeness
10. 36:35Constructing univariate function
11. 46:16Zero freeness proof by contradiction
12. 46:37Matchings application
13. 51:15Deforming polynomials
14. 54:07Asano-Ruelle contractions
15. 59:27Summary

" related talks

• 49mDiscrete Optimization using Log-Concave PolynomialsNima Anari · Hyperbolic Polynomials and Hyperbolic Programming
• 27mSharp Matrix ConcentrationMarch Boedihardjo · Deep Learning Theory Symposium 2021
• 49mInfluences in Gaussian SpaceArnab Sen · Functional Inequalities in Discrete Spaces with Applications 2013
• 57mCompletely Log-Concave PolynomialsCynthia Vinzant · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 03mHigh Dimensional Geometry and Concentration IISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 01h 11m(Hidden) Symmetries of Computational Problems (continued)Michael Walter, Avi Wigderson · Geometric Methods in Optimization and Sampling Boot Camp
• 57mHigh Dimensional Geometry and Concentration ISantosh Vempala · Foundations of Data Science Boot Camp 2018
• 54mNegative Dependence and Lorentzian PolynomialsPetter Brändén · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)