Randomised algorithms for low temperature spin systems

A spin system is a general framework in which the vertices of a graph are assigned spins from a finite set. The local interactions between neighbouring spins give rise to a global weight, which describes the probability that the system is in the given configuration. Spin systems provide a framework for sampling and counting problems in computer science, graph homomorphism problems in combinatorics, and phase transition phenomena in statistical physics. Two natural computational problems associated to a spin system are counting (computing the aggregate weight of all spin configurations) and sampling (constructing a random spin configuration with probability proportional to its weight). In general, the problem of exact counting is computationally hard, and our attention therefore turns towards approximate counting, and the closely related problem of approximate sampling. In computer science, approximate counting and sampling for spin systems, such as the hard-core model on independent sets or the Potts model on colourings, are well-studied problems. In recent years, on bounded-degree graph classes, an intimate connection has been established between the computational complexity of approximate sampling and counting, and the the existence of phase transitions in corresponding statistical physics models. Roughly speaking, there is a phase transition between a 'high-temperature' regime and a 'low temperature' regime. In the hightemperature regime, interactions between spins are weak and there is disorder in the model. Conversely, in the low temperature regime, interactions between spins are strong and the model is highly ordered - a typical configuration corresponds to one of some number of ground states, which limit the way that spins are assigned. This behaviour is reflected by the algorithmic properties of these models. At high-temperatures, there exists a variety of algorithmic techniques for approximate counting and sampling - examples include the Markov chain Monte Carlo (MCMC) method and correlation decay. At low temperatures, these approaches no longer succeed. Indeed, for many spin systems on many interesting classes of graphs, the problems of approximate counting and sampling are provably intractable. Recent research has sought to understand the algorithmic behaviour of spin systems such as the hard-core and Potts models on graphs such as the integer lattice and the random regular graph, the latter of which can be seen as an 'average case' instance of a regular graph. A detailed algorithmic and probabilistic understanding of these models has been developed, and has resulted in efficient low temperature algorithms. This is in contrast to the case of arbitrary bounded-degree graphs, where efficient algorithms can usually only be achieved in the high-temperature regime. These approaches typically use the truncated Taylor series approach of Barvinok to approximate the log partition function of a certain convergent series expansion. As such, they rely on tools from the complex analysis literature, and typically have running times of the form n O(log ∆) , where ∆ is the maximum degree of the input graph. The work in this thesis can be seen as part of this same program - we develop efficient algorithmic approaches for approximate counting and sampling in low temperature spin systems, in a variety of different settings. We present a Markov chain based approach to approximate counting and sampling from spin systems such as the hard-core and Potts models. Using combinatorial and probabilistic techniques, we prove fast running times for these algorithms. Our results apply to classes of graphs such as the integer lattice, the random regular graph, and bounded-degree expanders, and they apply in a similar range of parameters to existing results. We also generalise these techniques to any spin system in which the interactions between spins are sufficiently strong, and to classes of random graphs of possibly unbounded degree.