A Poly-time Deterministic Algorithm for Simply Exponential Approximation...
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Presents a deterministic polynomial-time algorithm that produces a simply exponential approximation for counting problems; it builds on ideas from scaling algorithms, real-stability/zero-free regions of polynomials, and Gurvits’s method for the Van der Waerden conjecture. The approach connects analytic bounds on partition-function zeros with combinatorial counting to achieve deterministic approximation guarantees without relying on randomization.
AI-written summary · about