Inapproximability of the Independent Set Polynomial in the Complex Plane

on YouTube ↗54m

" summary

Shows Sharp-P hardness of approximating the independent-set polynomial (partition function) outside the cardioid region: approximating its norm or angle is intractable even for bounded-degree, bipartite graphs. Reduction encodes exact counting via multivariate activities simulated by bounded-degree gadgets and Fibonacci-like tree construction that converges to a repelling fixed point of an associated rational map. Proof uses complex dynamics (Julia/Fatou theory) to produce dense target values from integer-coefficient polynomials and contracting maps to boost precision, plus degree-reduction and claw-free real-root arguments.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:50Independent set polynomial
3. 7:17Detour: Lovász Local Lemma
4. 8:01Related works
5. 18:24Single activity Reduction needed
6. 20:57Implementing activity at a vertex
7. 28:25Complex detour
8. 32:48Getting close to a repelling fixpoint
9. 40:14Back to game plan
10. 41:10E-covering of the neighborhood of
11. 45:06Exponential precision near
12. 47:11Recap