The Complexity of Approximating Small Degree Boolean #CSP

on YouTube ↗34m

" summary

Classifies the complexity of approximately counting solutions to Boolean constraint satisfaction problems when each variable appears in only a small number of constraints (small degree). Uses the framework of #CSP and focuses on approximation complexity for bounded-degree instances, identifying which constraint types and degree bounds yield tractable approximation algorithms (e.g., FPRAS) versus intractability (e.g., #P-hard to approximate).

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:15Counting CSP
3. 1:18Outline
4. 4:00#CSP over large domain
5. 4:25#CSP with degrees at most three
6. 6:22Examples
7. 8:12Dichotomies for Holant
8. 10:35Complexity of Approximate Counting
9. 13:20A non-example from weighted version
10. 18:49A non-example without Pinning
11. 19:50Single symmetric relation
12. 21:09Partial Classification (d 3)
13. 22:06Monotone Relations
14. 24:50d=5 (a conjecture)
15. 25:41d=5 (an attempted proof)
16. 29:02Holant Problems (d=2)
17. 30:19Counting Edge Covers
18. 30:53b-matching and b-edge-cover
19. 31:35Taking Home Messages