Approximation Algorithms for Partition Functions of Edge-Coloring Models

on YouTube ↗49m

" summary

Describes approximation algorithms for partition functions of edge-coloring models, focusing on techniques to compute or approximate these partition functions efficiently. Discusses algorithmic approaches and their relation to the classification program in counting complexity, likely involving connections to graph theory and computational complexity concepts mentioned in the programme.

AI-written summary · about

" chapters (16)

1. 0:00Start
2. 0:32Introduction: FPTAS for partition functions
3. 3:02Introduction: QPTAS for partition functions
4. 6:52Contents of the presentation
5. 7:11Partition functions of edge-coloring models
6. 11:39An example: counting perfect matchings
7. 15:53Where do you find edge-coloring models?
8. 19:55Counting graph homomorphisms
9. 21:31Main result
10. 25:10Proof high level overview
11. 30:01Approximating polynomials II
12. 33:28Computing derivatives I
13. 36:23Proof. high level overview
14. 36:43Zero-free regions
15. 38:19Phase transitions
16. 42:15Further work