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.

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.