Frontiers of Statistical Mechanics and Theoretical Computer Science (24w5169)


Tyler Helmuth (Durham University)

Jane Gao (University of Waterloo)

(University of Illinois, Chicago)

(Georgia Institute of Technology)

(Universidad Nacional Autónoma de México)


The Banff International Research Station will host the “Frontiers of Statistical Mechanics and Theoretical Computer Science” workshop in Banff from August 11 - 16, 2024.

A fundamental technological and scientific task is to approximately sample from very high-dimensional probability distributions. This arises, for example, if one wants to describe what a typical solution to a constraint satisfaction problem (e.g., scheduling/resource allocation) looks like. It turns out that understanding high-dimensional probability distributions is often equivalent to understanding (weighted) counting problems. This is also a central question in a fundamental field of physics known as statistical mechanics, where the goal is instead to understand the basic properties of matter based on the fact that matter is comprised of an enormous number of interacting constituent pieces (e.g., atoms, molecules, etc.). The existence of common question of interest in
these fields has a long history, dating back to the discovery of Markov Chain Monte-Carlo methods, which are now ubiquitous in academic and industrial settings.

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.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada’s Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta’s Advanced Education and Technology, and Mexico’s Consejo Nacional de Ciencia y Tecnología (CONACYT).