Approximation algorithms and inapproximability of partition functions of spin systems

Thesis

Over the past 30 years, the study of counting problems has become an interesting and important work. The framework of counting problems can capture applications in diverse fields, such as graph colouring and homomorphism in graph theory, and the Ising and Potts model from statistical physics. In this thesis, we will discuss my recent research work focusing on this area.

In Chapter 1, the basic notions and definitions of counting problems will be introduced. Because of the hardness result of computation complexity for counting problems, we will mainly consider whether we have efficient approximation algorithms for counting problems.

In the algorithmic part, one of the most exciting research is to establish the connection between the uniqueness phase transition of spin systems and the approximability phase transition of computing partition functions. In Chapter 2, we first discuss some basic methods of designing approximation algorithms, including the connection between sampling and counting and the correlation decay approach. These methods will be used in Chapter 4 and 5. In Chapter 3, we will discuss the uniqueness threshold for the antiferromagnetic Potts model on d-ary trees and introduce our results for small q. Chapter 4 and 5 contain two examples of counting and sampling in the uniqueness regime. We designed approximation algorithms for counting the number of 4-colourings on cubic graphs and sampling from the Potts model on random regular graphs in the uniqueness regime.

In the complexity part, a classification result for the complexity of approximate counting Boolean Constraint Satisfaction Problems on bounded-degree instances will be introduced in Chapter 6. We focused on whether, for all Boolean constraint languages Γ, there is a “barrier” value ∆0 such that for all ∆ > ∆0, the counting problem of Boolean CSP is computationally hard to approximate, and completely classified the complexity of this problem.

Authors: Yang, K

• DOI: 10.5287/ora-d5a44qm22
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Approximation algorithms