CAREER:Phase Transitions in Algorithms, Complexity, and Geometry

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Gibbs measures (or Boltzmann distributions) originated in statistical mechanics to model the phases of matter, but have since found numerous practical applications in statistics, machine learning, coding theory, and mathematical physics due to their simple encoding of complex dependencies. Two algorithmic tasks associated to Gibbs measures are essential in applications: sampling from a given model and efficiently approximating its normalizing constant, the partition function. This project aims to elucidate the connection between phase transitions in the underlying statistical physics model and the computational complexity of these two problems. The project features an integrated research and education plan, with the complementary goals of advancing fundamental knowledge of Gibbs measures and improving interdisciplinary mathematical education. The educational plan has activities aimed at three levels: outreach workshops to introduce high school students to mathematical research; the creation of tools for undergraduate instructors to implement effective pedagogical techniques; and the development of new graduate courses in applications of statistical physics across disciplines. More specifically, the research has three main goals. First, to develop efficient sampling algorithms for Gibbs measures in the low temperature, phase coexistence regime for models with a bounded number of ground states. Second, to make the powerful but non-rigorous cavity method from statistical physics into a rigorous mathematical tool for understanding the algorithmic tractability of random computational problems. Third, to understand fundamental geometric objects in high dimensions -- sphere packings, sphere coverings, and spherical codes -- by utilizing tools and insights from statistical physics. The pursuit of these three goals will introduce new probabilistic methods in computer science, statistics, and combinatorics. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.