Randomised algorithms for low temperature spin systems

Thesis

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 assoc...

Expand abstract

Authors: Stewart, J

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: expander graph; hard core model; Markov chains; approximate counting; approximation algorithms; randomised algorithms; Potts model; aproximate sampling; random graph
• Subjects: Algorithms; Theoretical computer science; Probability; Graph theory