Partition functions Zeros, unstable dynamics and complexity

This thesis considers the complexity of approximating the partition functions of the ferromagnetic Ising model and of the hard-core model (independence polynomial) within the class of bounded degree graphs. It is known that the absence of zeros essentially implies that approximation is easy. In this thesis the inverse is proved: the presence of zeros implies that approximation is #P hard. The most important step of the proof is relating both the "zero parameters" and the "#P hard parameters" to the set of parameters around which a related set of functions, namely the occupation ratios, behaves chaotically. The first two chapters contain the proof of the main theorem for the ferromagnetic Ising model and the independence polynomial respectively. Chapters 3 and 4 concern the set of zeros of the independence polynomial for bounded degree graphs. In Chapter 3 it is shown that zeros of Cayley trees are not extremal within the set of zeros of all bounded degree graphs, something that was previously conjectured. In Chapter 4 a very precise description of the set of zeros is given as the degree bound goes to infinity.