Approximate Counting via Correlation Decay

on YouTube ↗48m

" summary

Gives a concrete criterion (the uniqueness/contracting condition) that guarantees a deterministic FPTAS for partition functions and vertex marginals of two‑state spin systems on graphs of max degree Δ, and matches known hardness when the criterion fails. Builds on a self-avoiding walk tree reduction, truncation to logarithmic depth, and a carefully chosen potential function that amortizes derivatives to prove contraction; extends the approach to multi‑spin and hypergraph problems (colorings, edge covers) and it works where sampling methods previously required.

AI-written summary · about

" chapters (28)

1. 0:00Intro
2. 1:29Outline
3. 2:23Counting Problems
4. 4:52Approximate Counting
5. 5:54Counting vs Distribution
6. 9:50Spin Systems
7. 12:22Gibbs Measure
8. 14:10Constraint Satisfaction Problems
9. 15:24Some Tasks
10. 15:54Belief Propagation
11. 18:12Weak Correlation Decay
12. 21:59Two-State Spin System
13. 24:21Uniqueness Condition
14. 26:24Hardcore Model [Weitz 2006]
15. 27:36Self Avoiding Walk Tree
16. 29:24Ising Model Sinclair, Srivastava, and Thurley 2011
17. 29:55Non-Monotonicity
18. 30:18Our Results [Li, L., Yin 2012,13]
19. 33:19From correlation decay to FPTAS
20. 34:52Computational Efficient Correlation Decay
21. 35:43Proof Sketch for Correlation Decay
22. 37:31Potential Function
23. 40:20Multi-spin and Multi-part systems
24. 40:44Computation Tree
25. 41:52Coloring
26. 42:17Multi-spin System
27. 42:38Counting Edge Covers
28. 45:15A mathematical problem