Frontiers of Statistical Mechanics and Theoretical Computer Science Workshop Series

A central question in theoretical computer science concerns computational phase transitions that separate parameter regimes for which efficient algorithms do/do not exist. It is not a coincidence that this terminology has been borrowed from the physical sciences: there are, in some instances, rigorous links between computational and physical phase transitions. This confluence has led to an exciting research area exploring these connections and transferring ideas between fields.

This workshop series is aimed at promoting further interaction between the theoretical computer science and mathematical physics communities. We hope this contributes to the development of new techniques for algorithms, statistical mechanics, and combinatorics, as well as the discovery of further common research interests.

An important task in many scientific and technological areas is to approximately sample from very high-dimensional probability distributions. This arises, for example, when trying to construct timetables, or to test if data comes from a known (but complicated) source. Mathematically, understanding high-dimensional probability distributions is often equivalent to understanding a combinatorial task of (weighted) counting. In turn, weighted counting problems are central to the field of physics known as statistical mechanics, where the goal is to understand the basic properties of matter based on the fact that matter is comprised of an enormous number of interaction constituent pieces (e.g., atoms, molecules, etc.). The existence of common question of interest in these fields has long roots, dating back to the discovery of Markov Chain Monte-Carlo methods, which are now ubiquitous in academic and industrial settings. These fields turn out to share far more than a common mathematical language. In recent years we have learned that there are precise relations between the different phenomena of interest in these fields. In particular, there are precise contexts in which computational and physical phase transitions can be related to one another. The full extent and nature of commonalities and differences between these phenomena remain unclear, and this workshop aims to advance our understanding. This will be achieved by bringing together world-leading researchers from all three fields, allowing for the insights of these three fields to be applied to one another.

In recent years there have been profound discoveries of deeper ties between the subjects of computation, sampling, and mathematically rigorous statistical mechanics. We have learned that there are precise contexts in which computational and physical phase transitions can be related to one another. The extent of these relationships is not yet understood, and this workshop aims to advance our understanding. The discoveries of the past years have shown that the differing perspectives and tools of these fields can lead to new and powerful insights when applied to one another. This workshop is dedicated to taking advantage of this interdisciplinary viewpoint to make progress both within individual fields, and in our understanding of how different notions of phase transitions are theoretically (and practically) related to one another.

This hybrid workshop featured research talks from probabilists, computer scientists, and combinatorialists from around the world on Zoom. Students were invited to participate in-person at UIC in Chicago and Durham in the UK and there were in-person tutorial lectures for these participants.

Image by Matthis Lehmkuhler.

Mathematical physicists have developed several tools, including the cluster expansion, to prove the absence of a phase transition. Recently, these ideas have been used extensively for the development of algorithms, i.e., to verify the absence of a computational phase transition. Conversely, computer science techniques have lead to improvements in bounds in long-standing problems in statistical mechanics. This mini-workshop aims to bring these two communities into closer contact, to exchange ideas and problems, and to spur further progress.