Computing the Independence Polynomial in Shearer's Region for the LLL

on YouTube ↗30m

" summary

Gives a constructive LLL method that starts from a fractional coloring and rounds coordinates one by one while keeping the point inside Shearer's region, proving one of the two rounding choices always preserves feasibility. Builds a deterministic approximation algorithm for the multivariate independence polynomial whenever the input vector has a (1+α) slack in Shearer’s region, running in quasi‑polynomial/subexponential time in the worst case. Uses a correlation‑decay/Weitz generalization to handle multivariate and complex parameters and yields a deterministic LLL construction under slack.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 0:34The Lovász Local Lemma
3. 2:00Example: 2-colorability of hypergraphs
4. 5:01History of the Algorithmic LLL
5. 6:08Algorithm dynamics
6. 8:39The Feasible Region
7. 12:06The Univariate Feasible Region
8. 14:45Preserving feasibility: a proof of existential LLL
9. 20:13Main algorithmic results
10. 23:59Hard core model and counting weighted independent sets