The independence polynomial arises in statistical physics as the partition function of the Hard-core model. Its value in the value 1 counts the number of independent subsets of a graph, a computationally hard problem. In fact, exact computation of the independence polynomial is hard for most parameter values.

Instead of exact computation, one can look for efficient algorithms to approximately compute values of the independence polynomial. In current joint work with David de Boer, Pjotr Buys, Lorenzo Guerini and Guus Regts, all from the University of Amsterdam, we characterize the parameters for which approximation is hard: the closure of these parameters contains the closure of the zero-locus, which in turn coincides with the activity locus of a related family of rational functions.

For graphs of large bounded degrees we can give a more precise description of the domain where effective algorithms exist. Our method relies upon classical results in transcendental dynamics. In this talk I will focus on the relationship with complex dynamical systems.