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

Open Access
Authors
Publication date 03-2024
Journal Mathematical Proceedings of the Cambridge Philosophical Society
Volume | Issue number 176 | 2
Pages (from-to) 459-494
Organisations
  • Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
Abstract
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.
Document type Article
Language English
Published at https://doi.org/10.1017/S030500412300052X
Downloads
Permalink to this page
Back