Summary: | 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.
|