Collaborative Research: AF: Small: Phase Transitions in Sampling Related Problems

Graphical models are a widely used tool to succinctly represent high-dimensional data and to understand the fundamental building blocks and interactions of physical and biological systems. These models have appeared in a variety of scientific fields. In physics they are used to understand the thermodynamic properties of ferromagnetic materials and are integral in the study of phase transitions in physical systems.

In biology these models are a fundamental tool for inferring evolutionary history using genetic data in phylogenetic models. Graphical models are ubiquitous in machine learning for computational tasks such as Bayesian inference. This project addresses fundamental computational tasks that are crucial for studying, constructing, and utilizing graphical models.

The project will involve undergraduate students in research involving graphical models in social science settings.

There are two core tasks for studying graphical models: learning and sampling. The learning problem is focused on inferring the inner structure of the underlying graphical model from the macroscopic behavior of the system. In contrast, the goal of the associated sampling problem is to efficiently simulate the thermodynamic behavior of a learned or inferred graphical model.

This project will develop new algorithms, and more generally understand the computational complexity of sampling and learning as well as several related problems. A common theme in this project is connecting the computational complexity of these sampling- and inference-related problems with statistical-physics phase transitions.

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.