Spin systems—networks where neighbouring nodes influence each other’s behaviour—are everywhere, from magnetised materials to voting patterns, and this project aims to crack the mathematical code that governs them. The core problem is that the partition function, a polynomial that encodes a spin system’s essential properties, is notoriously hard to compute quickly. For decades, computer scientists have sought fast algorithms to approximate it, but many cases remain unsolved. This project attacks those gaps by linking the location of the function’s zeros—where it equals zero—to a property called strong spatial mixing, which measures how far a node’s influence ripples through the network. If the zeros are absent, the system mixes well and algorithms can run efficiently. This is fundamental science. Success would not immediately change daily life, but it would sharpen the theoretical toolkit for designing algorithms that underpin everything from network analysis to materials simulation. Past work on partition functions has unexpectedly enabled modern machine learning and statistical inference. A deeper, unified understanding of phase transitions across computer science, mathematics, and physics could eventually make those tools faster and more reliable—quietly improving how we model complex systems, from social networks to quantum materials.
View original technical description
This project is at the interface of theoretical computer science, mathematics and statistical physics. It aims to establish and leverage formal connections between different notions of phase transitions in these three different areas to make breakthroughs on long-standing questions. A phase transition is the phenomenon where a small change in some measure of a system (e.g. its temperature) results in a large change in its macroscopic behaviour (e.g. a material turning from a solid to a liquid). Phase transitions are currently at the forefront of study in several disciplines. The objects of study are spin systems. A spin system consists of some underlying network together with some temperature-type parameter that determines how strongly neighbouring nodes interact with each other. One then randomly assigns so-called spins to the nodes in such a way that spins of neighbouring nodes are correlated (e.g. in the ferromagnetic Ising model, nodes tend to prefer the more frequent spins amongst their neighbours). These spin systems exhibit remarkably rich behaviours; they originate in statistical physics, where they model gases, magnetism and other physical phenomena, but they have also found other applications e.g. in modelling voting behaviour. The partition function of a spin system is a complex function (in fact a polynomial) that captures a lot of important information about the system and about the underlying network. One of the major goals in theoretical computer science over the last 40 years has been to establish fast algorithms for approximating the partition function of spin systems: the project tackles several important unresolved questions here. The existence of such fast algorithms has recently been connected with the location of the zeros of partition functions, which in turn has been a topic of intense study in mathematics and statistical physics since the 1950s, and several challenges in this area are also addressed by the project. Another important goal of the proposal is to deepen our understanding of how strong spatial mixing for a spin system, that is the extent to which the spin of a node influences the spin at a distant nodes, affects the location of the zeros of its partition function. This proposal aligns most closely with the two EPSRC themes information and communication technology and mathematical sciences. The proposed research aims at establishing breakthrough results both in theoretical computer science and mathematics, and further aims to forge new connections with statistical physics to give a more unified understanding of problems in all three fields. Some of the specific highlights of the project are to attack the intensely studied problem of finding a fully polynomial-time approximation scheme for counting the number of proper colourings for graphs, to understand the algorithmic behaviour of the hardcore model when the underlying graph has some structure, to develop deterministic algorithms for approximating the Ising and monomer-dimer models, and to do all of this by understanding the zeros of the partition function in each of these cases. A powerful tool that we shall develop is to formulate and establish a general equivalence between strong spatial mixing of a spin system and the absence of zeros of the corresponding partition function.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know