Computation of the Multivariate Independence Polynomial by Correlation Decay

on YouTube ↗50m

" summary

Gives a deterministic algorithm that approximates the multivariate independence polynomial whenever the evaluation point stays a definite distance from the nearest negative root, adapting Weitz’s correlation decay algorithm to nonuniform sites by measuring errors against directional-derivative betas (a per-vertex yardstick). Analysis proves error contraction but incurs runtime exponential in 1/√(distance-to-root). A recent univariate analysis maps a segment under the recurrence to certify root-free points in the upper half-plane using a geometric convex-combination lemma, and predicts Im(λ) ~ Re(λ)^{1.5} near the negative root.

AI-written summary · about

" chapters (22)

1. 0:00Intro
2. 2:17Why is the partition function important?
3. 4:22Correlation decay vs. computational complexity
4. 6:51Motivation (2): The Lovász Local Lemma
5. 8:24General setup-dependency graphs
6. 9:44Shearer's Lemma
7. 11:25Computational questions
8. 16:49Checking membership in Shearer's region
9. 18:07More about the complex root-free region
10. 26:20About the techniques
11. 27:41Weitz's Approach
12. 29:51Our setting
13. 31:17Correlation decay analysis
14. 33:14The error sensitivity parameter
15. 34:11Summary of the correlation decay argument
16. 37:01The new root-free region
17. 38:29Example of the g(1) curve
18. 39:49Proof of root-freeness
19. 41:35From geometric combinations to linear combinations
20. 42:14Reduction to a univariate recurrence
21. 43:03Finishing the proof
22. 43:50Open questions