Sampling problems are fundamental in many areas of science and engineering, for example, statistics, artificial intelligence (machine learning and vision), and biology (phylogeny). Efficiency of sampling has impact on other important algorithms, for example, the speed of statistical tests and the reliability of estimators and classifiers. This project seeks to characterize combinatorial problems that admit efficient sampling algorithms. The research under this award addresses both sides of the characterization for a broad class of ubiquitous graphical models: 1) complexity theoretic obstacles to efficient sampling and 2) efficient sampling algorithms.
Recent results established a useful characterization for antiferromagnetic 2-spin models (for example, weighted independent sets and Ising model) in terms of the behavior of the model on regular trees. This created a connection to problems and techniques studied in the statistical physics community. This project aims to use the connection to the statistical physics and its techniques (for example, belief propagation recurrences) to generalize the characterization to models with more than two spins (multi-spin models, such as the Potts model, frequently occur in the applications). As a first step towards this generalization a relation between the efficiency of commonly used Markov chains (Glauber dynamics, Swendsen-Wang algorithm) and the behavior of the models on regular trees will be explored. Beside Markov chains the PI will also investigate other approaches to sampling problems (for example, dynamic programming and utilizing strong spatial mixing).
The product of the research will be efficient sampling algorithms and an improved understanding of obstacles to efficient sampling. The algorithmic problems, concepts, and techniques will be transferred to both undergraduate and graduate teaching (in the form of guided problems and implementation challenges). The award will support the training of two PhD students in the area of sampling and counting algorithms at the University of Rochester.
