Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial Article Swipe

PDF

Related Concepts

Independence (probability theory) Polynomial Mathematics Partition (number theory) Chaotic Partition function (quantum field theory) Function (biology) Rational function Time complexity Discrete mathematics Combinatorics Pure mathematics Computer science Mathematical analysis Statistics Artificial intelligence Physics Biology Evolutionary biology Quantum mechanics

David de Boer , Pjotr Buys , Lorenzo Guerini , Han Peters , Guus Regts ·

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2104.11615 · OA: W4388977671

The independence polynomial originates in statistical physics as the partition function of the hard-core model. The location of the complex zeros of the polynomial is related to phase transitions, and plays an important role in the design of efficient algorithms to approximately compute evaluations of the polynomial. In this paper we directly relate the location of the complex zeros of the independence polynomial to computational hardness of approximating evaluations of the independence polynomial. We do this by moreover relating the location of zeros to chaotic behaviour of a naturally associated family of rational functions; the occupation ratios.